189. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
1
2
3
4
5
6
输入: 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:
1
2
3
4
5
输入：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 - 10 <= k <= 105
进阶：
- 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为
O(1)的 原地 算法解决这个问题吗？
注：这道题有可能存在k > nums.length的情况。
例如：
输入
1
nums = [1,2]， k = 3
预期结果
1
[2,1]
解法1:未通过原因（超出时间限制）
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public void rotate(int[] nums, int k) {
int len = nums.length;
if (len == 1) return;
for (int i = 0; i < k; i++) {
int temp = nums[len - 1];
for (int j = len - 2;j >= 0;j--){
nums[j + 1] = nums[j];
}
nums[0] = temp;
}
}
}
超出时间限制的原因是：
LeetCode 测试用例中，( n ) 和 ( k ) 可达 10510^510^5 级别。例如：
- 输入：
n = 10^5（数组长度），k = 10^5（旋转步数）。 - 每次旋转移动 \(n-1 \approx 10^5\) 个元素，总操作次数为 \(k \cdot (n-1) \approx 10^5 \cdot 10^5 = 10^{10}\)次操作，远超 LeetCode 典型的 \(10^8\)操作时间限制
解法2:使用额外数组（非原地）
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) {
//首先处理k 如果k > len 那么需要
int len = nums.length;
k = k % len;
int[] res = new int[len];
int rest = 0;
for (int i = 0; i < len; i++) {
if (i < k) {
res[i] = nums[len - k + i];
} else {
res[i] = nums[rest++];
}
}
// 赋值回去
for (int j = 0; j < len; j++) {
nums[j] = res[j];
}
}
}
解法3:原地法(三段逆置)
首先优化k:k = k % len
然后做三件事：
- 逆置整个数组
- 逆置前k个数
- 逆置剩下的len - k个数
比如1，2，3，4，5，6，7，如果k = 3
- 逆置全部：7，6，5，4，3，2，1
- 逆置前k个数：5，6，7，4，3，2，1
- 逆置剩下7-3个数：5，6，7，1，2，3，4
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public void rotate(int[] nums, int k) {
//首先处理k 如果k > len 那么需要
int len = nums.length;
k = k % len;
reverse(nums, 0, len - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, len - 1);
}
public void reverse(int[] nums, int start, int end) {
int temp;
while (start < end) {
temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
}
