题目
题目链接：轮转数组
给定一个整数数组 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 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
第一种解法：额外数组
代码如下：
void rotate(int* nums, int numsSize, int k) { int newArr[numsSize]; for (int i = 0; i < numsSize; ++i) { newArr[(i + k) % numsSize] = nums[i]; } for (int i = 0; i < numsSize; ++i) { nums[i] = newArr[i]; } }
复杂度分析：
时间复杂度： O(n)，其中 n 为数组的长度。
空间复杂度： O(n)。
个人分析：
这种解法最妙的地方是（i+k)%numSize的运用，值得多想想，这里是使用了一个变长数组的写法，使用了额外的数组空间接收反转后的数组，再重新赋回原数组。
举个例子：
nums[ ]={1,2,3,4,5},k=2,反转后应是nums[ ]={4,5,1,2,3};
初始条件：i=0 k=2 numsSize=5 第一趟 i=0 (i + k) % numsSize=2 newArr[2]=nums[0] newArr[]={ , ,1, , } 第二趟 i=1 (i + k) % numsSize=3 newArr[3]=nums[1] newArr[]={ , ,1,2, } 第三趟 i=2 (i + k) % numsSize=4 newArr[4]=nums[2] newArr[]={ , ,1,2,3} 第三趟 i=3 (i + k) % numsSize=0 newArr[0]=nums[3] newArr[]={4, ,1,2,3} 第四趟 i=4 (i + k) % numsSize=1 newArr[1]=nums[4] newArr[]={4,5,1,2,3} i=numsSize 终止第一个循环
最后将利用for循环将newArr[ ]中的元素遍历赋给nums数组即可。
第二种解法：环状替换
代码如下：
//最大公约数 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } //交换 void swap(int* a, int* b) { int t = *a; *a = *b, *b = t; } void rotate(int* nums, int numsSize, int k) { k = k % numsSize; int count = gcd(k, numsSize); for (int start = 0; start < count; ++start) { int current = start; int prev = nums[start]; do { int next = (current + k) % numsSize; swap(&nums[next], &prev); current = next; } while (start != current); } }
复杂度分析：
时间复杂度：O(n)，其中 n 为数组的长度。每个元素只会被遍历一次。
空间复杂度：O(1)。我们只需常数空间存放若干变量。
个人分析：
首先讲讲这里的gcd函数是一个求最大公约数的自定义函数，有很多小伙伴可能不理解这种写法，可以替换成下面这种常规的辗转相除写法：
int gcd(int a, int b) { while(a%b) { int r=a%b; a=b; b=r; } return b; }
swap是常用的交换函数就不多讲了，这种写法的主要思路是将间隔为k的元素逐个向后替换，再将该间隔最后一个元素与开头替换，求k与numsSize的最大公约数是为了将不同间隔数分组，设定循环次数，便于遍历交换。
举个例子：
nums[ ]={1,2,3,4,5,6},k=2,反转后应是nums[ ]={5,6,1,2,3,4};
初始条件：start=0 k=2 numsSize=6 第一趟 prev=nums[0]=1 current=0 next=(current + k) % numsSize=2 nums[2]=1 prev=3 nums[]={1,2,1,4,5,6} current=2 next=(current + k) % numsSize=4 nums[4]=3 prev=5 nums[]={1,2,1,4,3,6} current=4 next=(current + k) % numsSize=0 nums[0]=5 prev=1 nums[]={5,2,1,4,3,6} current=0=start 终止do...while循环 第二趟 prev=nums[1]=2 current=1 next=(current + k) % numsSize=3 nums[3]=2 prev=4 nums[]={5,2,1,2,3,6} current=3 next=(current + k) % numsSize=5 nums[5]=4 prev=6 nums[]={5,2,1,2,3,4} current=5 next=(current + k) % numsSize=1 nums[1]=6 prev=2 nums[]={5,6,1,2,3,4} current=1=start 终止do...while循环 start=2=count 终止for循环
提一下这里的k=k%numsSize操作，我觉得是个优化吧，假设这里k=8，实际和k=2的最终结果是一样的，这样可以做性能上的优化吧，然后就是这里count是用于循环条件的，也可以不使用最大公约数的赋值写法，也可以在while循环里加一个变量记录被访问的元素，当count等于这个值时，结束遍历也可。
第三种解法：翻转数组
代码如下：
//交换 void swap(int* a, int* b) { int t = *a; *a = *b, *b = t; } //数组反转 void reverse(int* nums, int start, int end) { while (start < end) { swap(&nums[start], &nums[end]); start++; end++; } } void rotate(int* nums, int numsSize, int k) { k %= numsSize; reverse(nums, 0, numsSize - 1); reverse(nums, 0, k - 1); reverse(nums, k, numsSize - 1); }
复杂度分析：
时间复杂度：O(n)，其中 n 为数组的长度。每个元素被翻转两次，一共 n 个元素，因此总时间复杂度为 O(2n)=O(n)。
空间复杂度：O(1)。
个人分析：
这个算法的思路是先将整个数组先反转，再将前后两部分分别反转，个人认为比前两种写法更好理解一些。这里的反转的写法是采用前后指针的交换写法。同样的，举个例子：
nums[ ]={1,2,3,4,5},k=2,反转后应是nums[ ]={4,5,1,2,3};
初始条件： k=2 numsSize=5 第一趟 nums[]={5,4,3,2,1} 第二趟 nums[]={4,5,3,2,1} 第三趟 nums[]={4,5,1,2,3}
结语
这里的解法代码来自力扣官方，作者只是进行了详细的剖析和部分改动
方便大家理解和提升自己，学会多角度观察问题，解决问题。
有兴趣的小伙伴可以关注作者，如果觉得内容不错，请给个一键三连吧，蟹蟹你哟！！！
制作不易，如有不正之处敬请指出
感谢大家的来访，UU们的观看是我坚持下去的动力
在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！
