What is the easiest way to rotate an array using extra memory?

Create a new array of the same length and assign each element to index (i + k) % n, then copy back to the original array.

How do I handle k values greater than the array length?

Use modulo: effective rotation is k % n, ensuring indices wrap correctly without overflow.

Can I rotate the array in-place without extra space?

Yes, use cyclic replacement or the reverse method to move elements using two-pointer scanning while preserving values.

Why does cyclic replacement require tracking cycles?

Without tracking cycles, elements may be overwritten or moved multiple times, breaking the invariant of each element reaching its target position.

How does two-pointer scanning relate to Rotate Array?

It allows controlled movement of elements in-place or within subarrays, ensuring no overwrites occur and every element reaches its final rotated index.

#189

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

轮转数组

给定一个整数数组 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…

数组数学双指针

题目描述

给定一个整数数组 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 <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

进阶：

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

lightbulb

解题思路

方法一：三次翻转

我们不妨记数组长度为 $n$ ，然后将 $k$ 对 $n$ 取模，得到实际需要旋转的步数 $k$ 。

接下来，我们进行三次翻转，即可得到最终结果：

将整个数组翻转
将前 $k$ 个元素翻转
将后 $n - k$ 个元素翻转

举个例子，对于数组 $[1, 2, 3, 4, 5, 6, 7]$ , $k = 3$ , $n = 7$ , $k \bmod n = 3$ 。

第一次翻转，将整个数组翻转，得到 $[7, 6, 5, 4, 3, 2, 1]$ 。
第二次翻转，将前 $k$ 个元素翻转，得到 $[5, 6, 7, 4, 3, 2, 1]$ 。
第三次翻转，将后 $n - k$ 个元素翻转，得到 $[5, 6, 7, 1, 2, 3, 4]$ ，即为最终结果。

时间复杂度 $O(n)$ ，其中 $n$ 为数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(i: int, j: int):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1

        n = len(nums)
        k %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

speed

复杂度分析

指标	值
时间	complexity depends on the approach: extra array method is O(n), in-place cyclic replacement is O(n), and reversal method is O(n). Space complexity ranges from O(n) for the extra array to O(1) for in-place or reversal approaches.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that moves elements efficiently without overwriting unprocessed values.
question_mark
Pay attention if k exceeds array length and discuss modulo behavior.
question_mark
Expect discussion on trade-offs between extra memory versus in-place rotation.

warning

常见陷阱

外企场景

error
Overwriting elements before their new position is set in in-place methods.
error
Failing to account for k values larger than the array size, causing incorrect indexing.
error
Mismanaging cycle starts, resulting in infinite loops or missing elements during cyclic replacement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Rotate the array to the left instead of the right using similar two-pointer scanning logic.
arrow_right_alt
Rotate a multidimensional array row-wise or column-wise by k steps.
arrow_right_alt
Rotate only a subarray segment while leaving other elements intact.

help

常见问题

外企场景

继续练习

#167 两数之和 II - 输入有序数组 #268 丢失的数字 #287 寻找重复数