题目链接
轮转数组
题目描述
注意点
- 使用空间复杂度为 O(1) 的 原地 算法解决这个问题
解答思路
- 本题有多种思路，一种是复制nums数组，然后将k个位置后的值赋值给当前位置即可，但是空间复杂度为O(n)
- 还有一种思路是先将整个数组进行翻转，再将(0, k - 1)和(k, n)之间的数组各自进行翻转，最后得到的数组就是结果
代码
class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = k % n;reverse(nums, 0, n - 1);reverse(nums, 0, k - 1);reverse(nums, k, n - 1);}public void reverse(int[] nums, int start, int end) {while (start < end) {int tmp = nums[start];nums[start] = nums[end];nums[end] = tmp;start++;end--;}}
}
关键点
- 先将整个数组进行翻转，将后面k个数字移动前方，前面n - k个数字移到后方，再将这两部分分别进行翻转，保证顺序不变
