网络营销方案分享杭州seo公司哪家好
“路虽远，行则将至”
❤️主页：小赛毛
☕今日份刷题：轮转数组
题目链接：轮转数组
题目描述：
给定一个整数数组
nums，将数组中的元素向右轮转k个位置，其中k是非负数。示例1：
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]示例2
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
题解：
方法1：
如：
[1,2,3,4,5,6,7]|| [7,6,5,4,3,2,1] 挪动一个数据 右旋一次 合计右旋k次
- 时间复杂度：
O(K*N)or O(N^2)- 空间复杂度：O(1)
方法2：
（空间换时间）
如：
[1,2,3,4,5,6,7] k = 3|| （直接把后k个copy过来) [5,6,7]|| （再把前n-k个copy到后面) [5,6,7,1,2,3,4]
- 时间复杂度：O(N)
- 空间复杂度：O(N)
方法3:
如：
[1,2,3,4,5,6,7] k = 3|| （前n-k个逆置) [4,3,2,1,5,6,7]|| （后k个逆置) [4,3,2,1,7,6,5]|| （整体逆置) [5,6,7,1,2,3,4]
- 时间复杂度：O(N)
- 空间复杂度：O(1)
由于第三种方法可能没有那么容易思考到，所以我们这里只简单操作一下第二种方法：
代码：
void rotate(int* nums, int numsSize, int k){int*tmp=(int*)malloc(sizeof(int)*numsSize);int n=numsSize;k%=n;memcpy(tmp,nums+n-k,sizeof(int)*k);memcpy(tmp+k,nums,sizeof(int)*(n-k));memcpy(nums,tmp,sizeof(int)*(n));free(tmp);
}