描述
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
- 你可以使用空间复杂度为 O(1)的原地算法解决这个问题吗？
思想
拿到题目，开始想到了两个方法，一个是使用JDK提供的List实现，空间复杂度为 O(n),实现方法比较简单。另一种就是空间复杂度为 O(1) 的原地算法。用temp变量保存最后一个元素，倒序移位，每次旋转一步，多次旋转达到目的。考虑到K可能比length大，事先对k取余。代码如下：
class Solution {
public void rotate(int[] nums, int k) {
int temp = 0;
k = k%nums.length;
for (int i = 0; i < k; i++) {
// 每次旋转一位，旋转k次
temp = nums[nums.length-1];
for (int j = nums.length - 1; j >= 1; j--) {
nums[j] = nums[j - 1];
}
nums[0] = temp;
}
}
}结果
10:27
解答成功:
执行耗时:233 ms,击败了18.99% 的Java用户
内存消耗:39.1 MB,击败了11.03% 的Java用户
结果在时间和空间上并不是很好。
官方题解
使用额外的数组
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] newArr = new int[n];
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
System.arraycopy(newArr, 0, nums, 0, n);
}
}
环状替换
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
int count = gcd(k, n);
for (int start = 0; start < count; ++start) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % n;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
} while (start != current);
}
}
public int gcd(int x, int y) {
return y > 0 ? gcd(y, x % y) : x;
}
}
数组翻转
| 操作 | 结果 |
|---|---|
| 原始数组 | 1 2 3 4 5 6 7 |
| 翻转所有元素 | 7 6 5 4 3 2 1 |
| 翻转 [0,k mod n−1] 区间的元素 | 5 6 7 4 3 2 1 |
| 翻转 [k mod n−1, n-1] 区间的元素 | 5 6 7 1 2 3 4 |
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
}小结
数组翻转的第三种方法巧妙找到了数组翻转的本质，有助于解题和循环的使用。遇题要实现思考再动手解题，效率更高。