旋转数组

    数组 三步翻转法

    题目描述

    给定一个数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。要求使用 原地 算法，即不使用额外的数组空间。

    思路分析

    处理数组旋转问题时，最直观的想法是使用额外的空间来辅助。然而，如果我们希望在原数组上进行修改，就需要寻找元素索引变换的规律。当数组向右移动 k 个位置时，尾部的元素会循环回到数组头部。这种周期性的位移可以通过取模运算来简化，因为旋转一个数组长度的倍数相当于没有变化。

    三步翻转法是一种优雅且高效的解法。它基于一个有趣的观察：我们可以通过局部的翻转来实现全局的位移。首先，我们将整个数组进行翻转，这样数组的头部和尾部位置就完全颠倒了。随后，我们只需要分别针对前 k 个元素和剩余的元素进行局部翻转，就能让它们回到正确的相对顺序。这种方法巧妙地利用了翻转操作的对称性，只需遍历数组两次（一次整体，一次局部），即可在不借用辅助数组的情况下完成原位的旋转任务。

    示例代码

    /**
 * 旋转数组（三步翻转法）
 * 将数组中的元素向右轮转 k 个位置
 * @param {number[]} nums - 需要旋转的数组
 * @param {number} k - 旋转的步数
 * @returns {number[]} 旋转后的数组
 */
export function rotateNums(nums, k) {
  // 基础边界检查：如果不是数组、数组为空或只有一个元素，无需旋转
  if (!Array.isArray(nums) || nums.length <= 1) {
    return nums;
  }

  const len = nums.length;
  // 核心处理：
  // 1. k % len: 旋转 10 次对于长度为 7 的数组，实际上等于旋转 3 次
  // 2. (k % len + len) % len: 处理 k 可能为负数的情况，向左转转化为等价的向右转
  k = (k % len + len) % len;

  if (k === 0) return nums;

  /**
   * 辅助函数：翻转数组特定范围内的元素
   * @param {number[]} arr - 目标数组
   * @param {number} left - 起始下标
   * @param {number} right - 结束下标
   */
  function reverse(arr, left, right) {
    while (left < right) {
      // 使用解构赋值交换两个元素的值
      [arr[right], arr[left]] = [arr[left], arr[right]];
      left++;
      right--;
    }
  }

  // 三步翻转逻辑（向右旋转 k 的经典算法）：
  // 1. 翻转整个数组：[1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]
  reverse(nums, 0, len - 1);
  // 2. 翻转前 k 个元素：[7,6,5, 4,3,2,1] -> [5,6,7, 4,3,2,1] (假设 k=3)
  reverse(nums, 0, k - 1);
  // 3. 翻转剩余元素：[5,6,7, 4,3,2,1] -> [5,6,7, 1,2,3,4]
  reverse(nums, k, len - 1);

  return nums;
}

// 可视化测试用例
const list = [1, 2, 3, 4, 5, 6, 7];
rotateNums(list, 3);
console.log('旋转结果:', list); // 预期输出: [5, 6, 7, 1, 2, 3, 4]

    复杂度分析

    • 时间复杂度：O(n)，其中 n 为数组长度。总共进行了三次翻转操作，每次翻转的时间复杂度与处理的子数组长度成正比，总的时间复杂度仍为线性级别。
    • 空间复杂度：O(1)。只使用了常数个辅助变量，满足原地修改的要求。

    示例演示

    以 nums = [1, 2, 3, 4, 5, 6, 7] 且 k = 3 为例，核心步骤如下：

    1. 取模处理：k = 3 % 7 = 3。
    2. 翻转整个数组： [1, 2, 3, 4, 5, 6, 7] ➡️ [7, 6, 5, 4, 3, 2, 1]
    3. 翻转前 k 个元素（索引 0 到 2）： [7, 6, 5, 4, 3, 2, 1] ➡️ [5, 6, 7, 4, 3, 2, 1]
    4. 翻转剩余元素（索引 3 到 6）： [5, 6, 7, 4, 3, 2, 1] ➡️ [5, 6, 7, 1, 2, 3, 4]

    最终结果为 [5, 6, 7, 1, 2, 3, 4]。