旋转数组
方案一
循环K次将数组所有元素向后移动⼀位（代码不通过)
时间复杂度O(n2)
空间复杂度O(1)
void rotate(int* nums, int numsSize, int k) { while (k--) { int end = nums[numsSize - 1]; for (int i = numsSize - 1; i > 0; i--) { nums[i] = nums[i - 1]; } nums[0] = end; } }
- 时间复杂度过高，需要优化
方案二
申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中
时间复杂度O(n)
空间复杂度O(n)
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]; } }
- 记得最后要把新数组数据复制到原数组
- 时间复杂度降低了，可以通过
- 空间复杂度提升，仍可以优化
方案三
数组翻转
该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 kmodn 个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。
我们可以先将所有元素翻转，这样尾部的 kmodn 个元素就被移至数组头部，然后我们再翻转 [0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到最后的答案
时间复杂度：O(n)
空间复杂度：O(1)
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); }
