20 轮转数组

20.1 轮转数组解决方案

class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k = k % n;  // 如果 k 大于数组长度，取模减少不必要的旋转// 第一步：反转整个数组reverse(nums.begin(), nums.end());// 第二步：反转前 k 个元素reverse(nums.begin(), nums.begin() + k);// 第三步：反转剩下的 n-k 个元素reverse(nums.begin() + k, nums.end());}
};

解释：

• 模运算 (k = k % n): 这一步确保如果 k 比数组长度大，就只进行必要的旋转。
• 反转整个数组：这一步将数组中的最后 k 个元素放到了前面，并且顺序是反的。
• 反转前 k 个元素：这一步恢复了前 k 个元素的顺序。
• 反转剩下的元素：最后一步恢复了其余 n-k 个元素的顺序。
  时间复杂度：
• 时间复杂度：$O(n)$，其中 n 是数组的大小。反转数组和子数组的操作都是线性时间的。
• 空间复杂度：$O(1)$，这是原地操作，不需要额外的空间。
• 这种解法在时间和空间上都是非常高效的，适用于需要处理大数组的情况。

20.2 举例说明

假设我们有一个数组 nums = [1, 2, 3, 4, 5, 6, 7]，并且要求我们将数组向右旋转 k = 3 步。

目标： 将 nums 向右旋转 3 步，期望的输出是 [5, 6, 7, 1, 2, 3, 4]。

• 步骤 1：先进行一次整体反转：

  [7, 6, 5, 4, 3, 2, 1]
  

• 步骤 2：反转前 k = 3 个元素
  我们将数组的前 k = 3 个元素 [7, 6, 5] 反转：

  [5, 6, 7, 4, 3, 2, 1]
  

• 步骤 3：反转剩余的 n-k = 7 - 3 = 4 个元素
  我们对数组剩余的部分 [4, 3, 2, 1] 进行反转：

  [5, 6, 7, 1, 2, 3, 4]
  

• 结果：
  向右旋转了 3 步，得到了目标数组 [5, 6, 7, 1, 2, 3, 4]。