05 August 2008
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
1
2
3
4
5
6
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
1
2
3
4
5
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
翻转数组右边部分k个元素，如果可以用辅助数组，就直接 (i + k) % n来映射就行了，但是要求空间为常量，所以用额外数组来做不满足要求
1）用辅助变量来记录数组元素，将上面的解法要被替换的元素不直接放在最后的位置，而用一个temp来记录；2）数组翻转，先翻转整个数组，再翻转前k个数字，最后翻转后len - k个数字；
每一次移动都将数组中的一个元素 nums[i] 移动到 k 个位置后, 即 nums[(i+k)%n] ，将(i+k)%n 记为pos), 这个时候会出现元素覆盖问题，需要一个临时变量 temp 保存被覆盖的元素, 再将覆盖的元素用 pre 做记录，每次只需讲 pre 赋值给 nums[pos], 更新 pre 为被覆盖的元素，再寻找 nums[pos] 的下一个 元素 (pos+k)%n，直到所有元素都移动，即移动了n次（一共n个元素，每个都需要移动一次）
此时会存在一个问题，当 k 为 n 的因子时，会出现循环情况，例如 从 0 开始移动数组，最终会再回到0，而无法对其他的元素进行修改；此时只需要从 i=0 的下一个元素，即 i=1 开始移动数组元素即可，可以证明不会出现重叠的情况，只需循环到 i==k 时，即终止循环，nums 所有的元素移动完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public void rotate(int[] nums, int k) {
int len = nums.length,n = len;
int i = 0,pos = 0, pre = nums[pos],temp = nums[pos];
if(k % n == 0) return;
while (n-- != 0) {
pos = (pos + k) % len;
temp = nums[pos];
nums[pos] = pre;
pre = temp;
if (pos == i) {
pos = ++i;
pre = nums[pos];
temp = nums[pos];
}
}
}
}
数组翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return;
}
k %= nums.length;//k有可能比数组长度长
int len = nums.length;
reverse(nums, 0, len - 1);//全部数组翻转一遍
reverse(nums, 0, k - 1);//翻转前k个数组元素，翻转的目标范围
reverse(nums, k, len - 1);//翻转后面len - k个元素
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}