跳到正文
第 189 题中等

轮转数组

Rotate Array

把数组向右轮转 k 个位置，要求原地完成，尽量不使用额外数组。

在力扣中练习

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 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]
向右轮转 2 步: [3,99,-1,-100]

 

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

 

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

解题思路

主解法

三次反转 · O(1) 空间

整体反转，再分别反转前后两段

向右轮转 k 步，等价于把末尾 k 个数搬到前面。用额外数组很容易，但题目希望原地完成。

三次反转可以做到：

  1. 反转整个数组，末尾 k 个数跑到前面，但两段内部顺序都反了；
  2. 反转前 k 个数，恢复前半段的内部顺序；
  3. 反转剩下的 n-k 个数，恢复后半段。

自拟主例 [3,5,7,9,11,13]，k=2：整体反转得 [13,11,9,7,5,3]；反转前 2 个得 [11,13,9,7,5,3]；反转后 4 个得 [11,13,3,5,7,9]。

分步图解

k = 2，先对 n = 6 取模；原地轮转 k = 2 步。

k
2
nums
0
1
2
3
4
5
3
5
7
9
11
13
l
r
正在处理区间 [0, 5]
1 / 3
整体反转后，后两个数 11、13 到了最前面；但它们内部和前半段的顺序都反了。
分步图解

反转前 k 个数：11 13 9 7 5 3；前缀恢复成正向。

k
2
nums
0
1
2
3
4
5
11
13
9
7
5
3
l
r
正在处理区间 [0, 1]
1 / 3
分别反转前 k 段和剩余段，两段内部恢复正向，得到最终轮转结果。

时间 O(n)，空间 O(1)。注意先做 k %= n，否则 k 大于 n 时区间会越界。

时间 O(n)空间 O(1)

易错点

  • 忘记 k %= n：k 大于 n 时反转区间越界。
  • 第二次反转的范围写成 [0, n-k)：方向反了，前 k 个才是要恢复的段。
  • 三次反转顺序颠倒：先分段反转再整体反转，得到的不是轮转结果。
  • n = 0 或 k = 0 没有特判：反转空区间虽然安全，但边界要确认。
对照解法

额外数组 · 直接放置

复制一份，按 (i+k) % n 放回

时间 O(n)，但需要 O(n) 额外空间；主解法三次反转满足原地要求。

最直观的做法：先把原数组复制一份，再把每个元素写到 (i + k) % n。

时间 O(n)，空间 O(n)。它不容易写错，适合先验证轮转方向；如果题目允许额外空间，这也是可提交的解法。

  1. 1k %= n，复制原数组。
  2. 2i 从 0 到 n-1：nums[(i+k)%n] = copy[i]。
时间 O(n)空间 O(n)

易错点

  • 取模写成 i + k：i + k 可能超过 n，下标越界。
  • 直接在原数组上覆盖：还没读到的元素会被写掉。

代码与演示

主解法配有图解；对照解法用于比较思路、复杂度或实现方式。

演示输入nums = [3,5,7,9,11,13], k = 2

k = 2，先对 n = 6 取模；原地轮转 k = 2 步。

k
2
nums
0
1
2
3
4
5
3
5
7
9
11
13
l
r
正在处理区间 [0, 5]
1 / 5
查看 C++ 代码

延伸阅读

  • 三次反转也常用于“翻转字符串里的单词”“循环移位”等需要原地重排的题。
  • 如果要求向左轮转，把 k 换成 n-k 即可。