🔗 转轮数组

题目来源：189. 轮转数组 – 力扣（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,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(n) 时间，O(1) 空间

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k % len;  // 处理 k 大于数组长度的情况
        reverse(nums, 0, len - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, len - 1);
    }

    public void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 每次 reverse 操作为 O(n)，共执行 3 次，总体仍为线性时间。
• 空间复杂度：O(1)
  • 仅使用常数个额外变量（如 temp），满足原地修改要求。

---

🧩 解题思路

1. 核心思想：三次反转法
   利用反转操作巧妙地实现轮转，无需额外数组。
2. 数学原理：
   设数组长度为 n，轮转 k 步后：
   • 原数组后 k 个元素（[n-k, n-1]）移动到前 k 个位置
   • 原数组前 n-k 个元素（[0, n-k-1]）移动到后 n-k 个位置
   通过以下三步可实现：
   • 步骤 1：反转整个数组 → [n-1, n-2, ..., 0]
   • 步骤 2：反转前 k 个元素 → 将原后 k 个元素恢复为正序
   • 步骤 3：反转后 n-k 个元素 → 将原前 n-k 个元素恢复为正序
3. 举例说明：
   对 nums = [1,2,3,4,5,6,7], k = 3：
   • 步骤 1：反转整个数组 → [7,6,5,4,3,2,1]
   • 步骤 2：反转前 k=3 个 → [5,6,7,4,3,2,1]
   • 步骤 3：反转后 4 个 → [5,6,7,1,2,3,4] ✅
4. 边界处理：
   • k %= len：避免 k 大于数组长度，减少无效轮转。
   • 当 k == 0 时，无需操作。
5. 为什么能原地实现？
   • 反转操作本身可在原数组上完成。
   • 无需记录每个元素的新位置，通过整体操作达成目标。