题目描述：
给一个数组，将数组中的元素向右轮转 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
题目链接：https://leetcode.cn/problems/rotate-array
方法一：暴力穷举，直接旋转k次
void rotate(int* nums, int numsSize, int k) { while (k--) { int ret = nums[numsSize - 1]; int i; for (i = numsSize - 1; i > 0; i--) { nums[i] = nums[i - 1]; } nums[0] = ret; } } int main() { int nums[] = { 1,2,3,4,5,6,7 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int k = 3; rotate(nums, numsSize, k); int i; for (i = 0; i < numsSize; i++) { printf("%d ", nums[i]); } return 0; }
这个方法是最简单的，能够直接就想到的办法，但是它的时间复杂度偏高。
方法二：空间换时间
新建一个变长数组（部分编译器不支持变长数组，所以可能会有些会报错，但是OJ是支持的，可以直接在OJ上使用），先将下标大于k的的项放入新数组，然后再把剩余的项按顺序放入新数组。最后用新数组中的值，按照下标顺序覆盖原数组的值即可。
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]; } } int main() { int nums[] = { 1,2,3,4,5,6,7 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int k = 3; rotate(nums, numsSize, k); int i; for (i = 0; i < numsSize; i++) { printf("%d ", nums[i]); } return 0; }
newArr[(i + k) % numsSize] = nums[i];中%numsSize的原因是K值可能是大于这个数组长度的。
三、三步翻转法
三步翻转法是一个比较经典的方法，比较难想到，只能通过刷题来积累。第一个想到这个方法的人真是一个牛人。
//创建一个翻转函数，用来逆置数组 void reverse(int* nums, int begin, int end) { while (begin < end) { int tmp = nums[begin]; nums[begin] = nums[end]; nums[end] = tmp; begin++; end--; } } void rotate(int* nums, int numsSize, int k) { k = k % numsSize; reverse(nums, 0, numsSize - k - 1); reverse(nums, numsSize - k, numsSize - 1); reverse(nums, 0, numsSize - 1); } int main() { int nums[] = { 1,2,3,4,5,6,7 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int k = 3; rotate(nums, numsSize, k); int i; for (i = 0; i < numsSize; i++) { printf("%d ", nums[i]); } return 0; }
