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]

题目大意

给定一个整数数组 nums 和非负整数 k，将数组元素向右轮转 k 个位置（即每个元素向右移动 k 位，末尾元素移动到开头）。要求尽可能优化时间和空间复杂度。

核心解题思路：三次反转法

常规思路（如临时数组、多次右移）要么空间复杂度高（O (n)），要么时间复杂度高（O (nk)）。三次反转法通过巧妙的反转操作，实现 O (n) 时间复杂度 + O (1) 空间复杂度，是该问题的最优解法，核心原理如下：

  1. 处理 k 的冗余：若 k >= nums.size()，轮转 k 次等价于轮转 k % nums.size() 次（避免重复操作）。
  2. 第一次反转：反转整个数组，将末尾 k 个元素移到数组前部（但顺序颠倒）。
  3. 第二次反转：反转前 k 个元素，恢复其原始顺序。
  4. 第三次反转：反转剩余元素（从 k 到末尾），恢复其原始顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    // 确保函数名为rotate，参数正确
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if (n <= 1) return;
        
        // 处理k的冗余
        k %= n;
        if (k == 0) return;
        
        // 三次反转法
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};