hot 100 第十五题 15.轮转数组

2026-02-08 12:52:34 栏目：最新资讯 5 阅读

题目：

给定一个整数数组 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,2,3,4,5,6,7], k=3
目标:   [5,6,7,1,2,3,4]

观察规律:
原数组可以分为两部分：
[1,2,3,4] [5,6,7]
    ↓         ↓
后面k个移到前面

步骤:
1. 反转整个数组: [7,6,5,4,3,2,1]
2. 反转前k个:    [5,6,7,4,3,2,1]
3. 反转后n-k个:  [5,6,7,1,2,3,4] ✓

解法1: 使用额外数组（最直观）

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int[] temp = new int[n];
        
        // 复制到新数组
        for (int i = 0; i < n; i++) {
            temp[(i + k) % n] = nums[i];
        }
        
        // 复制回原数组
        for (int i = 0; i < n; i++) {
            nums[i] = temp[i];
        }
    }
}

解法2: 环状替换

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = 0;  // 已移动的元素个数
        
        for (int start = 0; count < n; 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;
                count++;
            } while (start != current);
        }
    }
}

解法三：三次反转法

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;  // 处理 k > n 的情况
        
        // 三次反转
        reverse(nums, 0, n - 1);        // 反转整个数组
        reverse(nums, 0, k - 1);        // 反转前k个
        reverse(nums, k, n - 1);        // 反转后n-k个
    }
    
    // 反转数组的 [start, end] 部分
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}
```

## 详细演示
```
nums = [1,2,3,4,5,6,7], k = 3

步骤0: k = 3 % 7 = 3 (处理k可能大于数组长度的情况)

步骤1: 反转整个数组 [0, 6]
[1,2,3,4,5,6,7]
 ↕           ↕
[7,6,5,4,3,2,1]

步骤2: 反转前k个 [0, 2]
[7,6,5,4,3,2,1]
 ↕ ↕
[5,6,7,4,3,2,1]

步骤3: 反转后n-k个 [3, 6]
[5,6,7,4,3,2,1]
      ↕     ↕
[5,6,7,1,2,3,4] ✓
```

## 为什么这样有效？

用图示理解：
```
原数组: A B C D E F G (n=7, k=3)
目标:   E F G A B C D

关键观察:
原数组 = [A B C D] [E F G]
         ← 左部分  ← 右部分
目标   = [E F G] [A B C D]

三次反转的逻辑:
1. 整体反转: [G F E D C B A]
   → 相当于把两部分都倒过来了

2. 前k个反转: [E F G D C B A]
   → 把右部分翻回正序

3. 后n-k个反转: [E F G A B C D]
   → 把左部分翻回正序