手帐 Blog

主题

复盘 · LC 48 旋转图像 ​

题目 ​

题意 ​

给定 n × n 二维矩阵，将图像顺时针旋转 90°。必须原地修改 matrix，不要另开整块新矩阵再拷回去。

映射关系：位置 (i, j) 上的值应落到 (j, n - 1 - i)。四个角形成长度为 4 的环。

边界：n = 1（不动）；偶数边长 / 奇数边长（中心格不动）。

涉及算法 ​

标签一句话
矩阵变换顺时针 90° = 先转置，再左右翻转每一行
原地四元组按层遍历，一次交换环上四个位置

教程对照：矩阵原地改写手感接 04 · 数组基础题手感；和 73 · 矩阵置零 同属「在矩阵上动手脚」。

评价我的解法 ​

独立 AC（21/21），用时很好；内存约 55MB、仅约 5%——多半是因为开了整张 isCheckArr。

思路：知道目标位置是 (j, n - 1 - i)，用 visited 标记避免重复交换。方向对，但实现偏「模拟交换」，面试不好口述，也浪费 O(n²) 空间。

我的代码（摘自 48-旋转图像/index.js，不含本地测例）：

javascript
var rotate = function (matrix) {
  const len = matrix.length;
  const isCheckArr = new Array(len);
  for (let i = 0; i < matrix.length; i++) {
    isCheckArr[i] = new Array(len);
    isCheckArr[i].fill(false);
  }
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      const k = len - i - 1;
      if (isCheckArr[i][j]) {
        continue;
      }
      const item = matrix[i][j];
      const other = matrix[j][k];
      matrix[i][j] = other;
      matrix[j][k] = item;
      isCheckArr[i][j] = true;
      isCheckArr[j][k] = true;
    }
  }
};

代码里几处值得改：

  1. 额外 O(n²) 空间：题目强调原地；visited 矩阵直接把空间档位打穿。
  2. 只做两两交换：顺时针本质是 4-环 (i,j) → (j,n-1-i) → …。用 visited + 两两 swap 能 AC，但推理成本高，不如「转置 + 行反转」或显式四元组一次转到位。
  3. 可读性：k = len - i - 1 没写注释，面试官很难跟你对映射。

小结：结果对、复杂度时间够用；缺的是标准模板和 O(1) 额外空间意识。

最佳题解 ​

转置 + 每行 reverse（最易口述）：

javascript
/**
 * @param {number[][]} matrix
 * @return {void}
 */
var rotate = function (matrix) {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const tmp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = tmp;
    }
  }
  for (let i = 0; i < n; i++) {
    matrix[i].reverse();
  }
};
  • 时间 O(n²)，额外空间 O(1)。
  • 为何更优：两步都是熟操作；不需要 visited；映射拆成「行列互换」和「水平翻转」，好记也好讲。

关联题目 ​

题为何相关
867. 转置矩阵本题第一步单独拿出来
54. 螺旋矩阵同日矩阵模拟
73. 矩阵置零矩阵原地约束

一句话带走 ​

旋转 90° 顺时针：转置 → 每行反转；别为原地再开一张 visited。