💡题目分析
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
💡解题思路
🚩思路1:暴力求解 — 旋转k次
假如我们要把数组 [1,2,3,4,5,6,7]，向右旋转3次
👇图解👇
第1步：定义一个临时变量 tmp，用来存放数组最后的元素7
第2步：把数组前 n-1 个值往后挪
第3步：把 tmp 的值放入前面空位置中去
👆这样就完成了 1 次轮转，如果要轮转 k 次，就需要循环 k 次就完成了
🔔接口源码：
void rotate(int* nums, int numsSize, int k) { k %= numsSize;//防止k大于numsSize int tmp = 0; for (int i = 0; i < k; i++) { tmp = nums[numsSize - 1]; for (int j = numsSize - 1; j > 0; j--) { nums[j] = nums[j - 1]; } nums[0] = tmp; } }
此方法：
时间复杂度：O(N^2) — 最坏情况
空间复杂度：O(1)
🚨但是这种解法是过不了的，LeetCode会限制效率，这种方法效率太低了
🚩思路2:额外开数组
以 空间换时间 的做法
👇图解👇
第1步：新开辟一个数组
第2步：把后 k 个元素放到新数组的前面
第3步：再把前 n-k 个元素放到新数组的后面（n是数组中元素总个数 也就是题目中的参数 numsSize）
🔔接口源码：
void rotate(int* nums, int numsSize, int k) { if (k > numsSize) { k %= numsSize; } int* tmp = (int*)malloc(sizeof(int) * numsSize); memcpy(tmp, nums + numsSize - k, sizeof(int) * k); memcpy(tmp + k, nums, sizeof(int) * (numsSize - k)); memcpy(nums, tmp, sizeof(int) * (numsSize)); free(tmp); tmp = NULL; }
此方法：
时间复杂度：O(N)
空间复杂度：O(N)
🚩思路3:三段逆置
🥰非常绝绝子的方法！！！
👇图解👇
第1步：对前 n-k 个逆置
第2步：对后 k 个逆置
第3步：整体逆置
此方法：
时间复杂度：O(N)
空间复杂度：O(1)
📍算法设计
先写一个逆置的函数来实现逆置的功能👇
void reverse(int* arr, int left, int right) { while (left < right) { int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++; right--; } }
🚨我们使用 reverse逆置函数的时候要注意：数组下标是从 0 开始的
🚨我们还需要注意一个问题：如果 k 超过了数组元素个数怎么办？
比如：数组是 [ 1 2 3 4 5 6 7] ，k = 8 的时候，此时数组元素个数为 7，而要求向右旋转 8 个位置，如果按照上面分析的情况，第一趟对前 n - k 逆置，也就是 7-8个逆置，难道对前 -1 个逆置吗？
仔细想一下最后的结果会是什么？
结果数组就是 [ 7 1 2 3 4 5 6 ]
🚨我们要记住这道题的核心叫 轮转数组，也就是当轮转的次数超过数组长度的时候，又是新的一轮了！
所以，如果 k 大于数组长度，故首先对 k 取余，然后再次旋转，这不会影响最终结果！
🔔接口源码：
void reverse(int* arr, int left, int right) { while (left < right) { int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k) { if(k>numsSize) { k%=numsSize; } reverse(nums, 0, numsSize-k-1); reverse(nums, numsSize-k, numsSize-1); reverse(nums, 0, numsSize-1); }
