原地旋转与轮转

数组轮转 k 位如何原地完成？

• 目标: 元素整体右移 k 位, 超出末尾的元素回到开头;
• 翻转法: 先整体翻转 → 再翻转 [0, k % n - 1] → 最后翻转 [k % n, n - 1];
• 三次翻转后位序正确;

function rotate(nums: number[], k: number): void {
  k %= nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
}

function reverse(nums: number[], start: number, end: number): void {
  while (start < end) {
    [nums[start], nums[end]] = [nums[end], nums[start]];
    start += 1;
    end -= 1;
  }
}

• 时间复杂度: O(n);
• 空间复杂度: O(1);

矩阵顺时针旋转 90 度如何原地完成？

• 位置映射: mat[row][col] 旋转后位于 mat[col][n - row - 1];
• 四个对称位置构成一个循环, 用临时变量依次搬移;
• 只需遍历左上角的 floor(n / 2) × floor((n + 1) / 2) 个位置, 每个位置处理完整一圈;

function rotateMatrix(matrix: number[][]): void {
  const n = matrix.length;
  for (let i = 0; i < Math.floor(n / 2); i++) {
    for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
      const temp = matrix[i][j];
      matrix[i][j] = matrix[n - j - 1][i];
      matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
      matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
      matrix[j][n - i - 1] = temp;
    }
  }
}

• 时间复杂度: O(n^2);
• 空间复杂度: O(1);

螺旋生成矩阵与螺旋遍历是什么关系？

• 生成是遍历的逆过程: 用同样的四边界收缩顺序把 1..n² 依次填入;
• 每访问一个位置就写入下一个数, 边界处理与遍历完全相同;
• 时间复杂度: O(n^2); 空间复杂度: O(n^2);