189. 轮转数组
题目描述
输入整数数组 nums 和非负整数 k。把数组整体向右循环移动 k 个位置：每移动一步，最后一个元素就挪到最前面。
直接在 nums 上修改，不需要返回值。页面展示的输出是修改后的 nums。k 可能大于数组长度。
示例 1
输入：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
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100]
解释：右移 1 步得 [99,-1,-100,3]，再移 1 步得 [3,99,-1,-100]。
数据范围
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 10 <= k <= 10^5
进阶：尽量想出多种做法，本题至少有三种不同思路。能否只用 O(1) 额外空间原地完成？
解题思路：三次翻转
k 先对 n 取模。整体翻转，再分别翻转前 k 个和后 n-k 个元素，即可把尾部移到前面且保持各段内部顺序。
为什么正确
每次翻转后，目标数组被拆成的两段位置关系已经正确，只需恢复段内顺序。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
k 可能大于数组长度，必须先 k%=n；空数组需按题目约束处理。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def rotate(self, nums,k):
n=len(nums); k%=n
def rev(i,j):
while i<j: nums[i],nums[j]=nums[j],nums[i]; i+=1; j-=1
rev(0,n-1); rev(0,k-1); rev(k,n-1)class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length; k %= n;
rev(nums, 0, n - 1); rev(nums, 0, k - 1); rev(nums, k, n - 1);
}
private void rev(int[] nums, int i, int j) {
while (i < j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; i++; j--; }
}
}class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size(); k %= n;
auto rev = [&](int i, int j) {
while (i < j) { swap(nums[i], nums[j]); i++; j--; }
};
rev(0, n - 1); rev(0, k - 1); rev(k, n - 1);
}
};func rotate(nums []int, k int) {
n := len(nums); k %= n
rev := func(i, j int) {
for ; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
}
rev(0, n-1); rev(0, k-1); rev(k, n-1)
}var rotate = function(nums, k) {
const n = nums.length; k %= n;
const rev = (i, j) => {
while (i < j) { [nums[i], nums[j]] = [nums[j], nums[i]]; i++; j--; }
};
rev(0, n - 1); rev(0, k - 1); rev(k, n - 1);
};function rotate(nums: number[], k: number): void {
const n = nums.length; k %= n;
const rev = (i: number, j: number): void => {
while (i < j) { [nums[i], nums[j]] = [nums[j], nums[i]]; i++; j--; }
};
rev(0, n - 1); rev(0, k - 1); rev(k, n - 1);
}其他解法
额外数组靠 O(n) 空间换取简单；环状替换沿置换环逐个搬动，三次翻转用翻转的组合得到轮转，两者都是原地 O(1) 空间。
解法 2：额外数组 时间 O(n)，空间 O(n)
新建一个长度为 n 的数组，把原数组下标 i 的元素放到新数组下标 (i+k) mod n 的位置。最后把新数组拷回原数组。
直接对应轮转的定义，不容易写错。需要 O(n) 额外空间，不满足进阶的原地要求。
from typing import List
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
res = [0] * n
for i in range(n):
res[(i + k) % n] = nums[i]
nums[:] = resclass Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n];
for (int i = 0; i < n; i++) res[(int) ((i + (long) k) % n)] = nums[i];
System.arraycopy(res, 0, nums, 0, n);
}
}class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res(n);
for (int i = 0; i < n; i++) res[(i + k) % n] = nums[i];
nums = res;
}
};func rotate(nums []int, k int) {
n := len(nums)
res := make([]int, n)
for i, v := range nums {
res[(i+k)%n] = v
}
copy(nums, res)
}var rotate = function(nums, k) {
const n = nums.length;
const res = new Array(n);
for (let i = 0; i < n; i++) res[(i + k) % n] = nums[i];
for (let i = 0; i < n; i++) nums[i] = res[i];
};function rotate(nums: number[], k: number): void {
const n = nums.length;
const res: number[] = new Array(n);
for (let i = 0; i < n; i++) res[(i + k) % n] = nums[i];
for (let i = 0; i < n; i++) nums[i] = res[i];
};解法 3：环状替换 时间 O(n)，空间 O(1)
从下标 start 出发，把当前元素放到 (cur+k) mod n，把被挤出的元素继续往后放，直到回到 start，完成一个环。可以证明共有 gcd(n, k) 个环，分别从 0 到 gcd(n, k)-1 出发各走一遍，每个元素恰好移动一次。
同样是 O(1) 空间，每个元素只写一次。需要理解环的个数为什么是 gcd(n, k)，比三次翻转难想到。
from math import gcd
from typing import List
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
for start in range(gcd(n, k)):
cur, prev = start, nums[start]
while True:
nxt = (cur + k) % n
nums[nxt], prev = prev, nums[nxt]
cur = nxt
if cur == start:
breakclass Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
int cnt = gcd(n, k);
for (int start = 0; start < cnt; start++) {
int cur = start, prev = nums[start];
do {
int nxt = (cur + k) % n;
int t = nums[nxt]; nums[nxt] = prev; prev = t;
cur = nxt;
} while (cur != start);
}
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
int cnt = gcd(n, k);
for (int start = 0; start < cnt; start++) {
int cur = start, prev = nums[start];
do {
int nxt = (cur + k) % n;
swap(nums[nxt], prev);
cur = nxt;
} while (cur != start);
}
}
};func rotate(nums []int, k int) {
n := len(nums)
k %= n
g := n
for b := k; b != 0; {
g, b = b, g%b
}
for start := 0; start < g; start++ {
cur, prev := start, nums[start]
for {
nxt := (cur + k) % n
nums[nxt], prev = prev, nums[nxt]
cur = nxt
if cur == start {
break
}
}
}
}var rotate = function(nums, k) {
const n = nums.length;
k %= n;
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const cnt = gcd(n, k);
for (let start = 0; start < cnt; start++) {
let cur = start, prev = nums[start];
do {
const nxt = (cur + k) % n;
[nums[nxt], prev] = [prev, nums[nxt]];
cur = nxt;
} while (cur !== start);
}
};function rotate(nums: number[], k: number): void {
const n = nums.length;
k %= n;
const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
const cnt = gcd(n, k);
for (let start = 0; start < cnt; start++) {
let cur = start, prev = nums[start];
do {
const nxt = (cur + k) % n;
[nums[nxt], prev] = [prev, nums[nxt]];
cur = nxt;
} while (cur !== start);
}
};