矩阵数组专题：Rotate Image、Set Matrix Zeroes、Valid Sudoku

摘要

本篇覆盖三道以二维数组（矩阵）为载体的经典面试题：Rotate Image（LeetCode 48）、Set Matrix Zeroes（LeetCode 73）、Valid Sudoku（LeetCode 36）。这三道题看似独立，核心考察点却高度一致：如何用最小的额外空间完成原地矩阵操作，以及如何设计高效的状态标记方案。矩阵题是面试中的常客，掌握这些技巧能应对大量二维数组变体。

第 1 章二维数组的坐标变换基础

1.1 矩阵旋转的数学本质

旋转矩阵是矩阵操作中最基础的变换之一。在讨论代码之前，先建立坐标变换的数学直觉。

对于 $n \times n$ 矩阵中坐标为 $(r, c)$ 的元素（r 是行，c 是列，均从 0 开始）：

变换类型	新坐标	直觉说明
顺时针旋转 90°	$(c, n - 1 - r)$	原来的列变成行，行从下往上变成列
逆时针旋转 90°	$(n - 1 - c, r)$	原来的行变成列，列从右往左变成行
旋转 180°	$(n - 1 - r, n - 1 - c)$	完全翻转，等价于上下翻转再左右翻转
主对角线转置	$(c, r)$	行列互换， $(r, c) \to (c, r)$
副对角线转置	$(n - 1 - c, n - 1 - r)$	行列互换再双向取反

这些公式不需要死记硬背，理解了一个之后，其他的可以通过组合推导出来。

1.2 顺时针 90° = 转置 + 水平翻转

关键分解：顺时针旋转 90° 等价于：

沿主对角线转置（行列互换）： $(r, c) \to (c, r)$
水平翻转（左右翻转）： $(r, c) \to (r, n - 1 - c)$

验证：两步组合后， $(r, c) \to (c, r) \to (c, n - 1 - r)$ ，这正是顺时针 90° 的坐标变换 $(r, c) \to (c, n - 1 - r)$ 的逆推结果（注意变量名的含义）。

这个分解的价值在于：转置和翻转都可以原地完成，从而实现 $O (1)$ 额外空间的原地旋转。

第 2 章 LeetCode 48：旋转图像

2.1 题目

LeetCode 48 - Rotate Image（中等）

给定一个 $n \times n$ 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。不要使用另一个矩阵来旋转图像，在原地旋转。

输入:               输出:
[[1,2,3],          [[7,4,1],
 [4,5,6],    →      [8,5,2],
 [7,8,9]]           [9,6,3]]

2.2 利用分解的原地算法

第一步：主对角线转置（行列互换）

对于 i < j 的位置 $(i, j)$ ，交换 matrix[i][j] 和 matrix[j][i]：

转置前:          转置后:
1 2 3            1 4 7
4 5 6    →       2 5 8
7 8 9            3 6 9

第二步：每行左右翻转

将每一行的元素对称交换：

转置后:          左右翻转后:
1 4 7            7 4 1
2 5 8    →       8 5 2
3 6 9            9 6 3

两步完成后，就是顺时针旋转 90° 的结果。

2.3 代码实现

public void rotate(int[][] matrix) {
    int n = matrix.length;
    
    // 第一步：沿主对角线转置（只遍历上三角，避免重复交换）
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {  // j 从 i+1 开始，避免自交换或重复
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    
    // 第二步：每行左右翻转
    for (int i = 0; i < n; i++) {
        int left = 0, right = n - 1;
        while (left < right) {
            int tmp = matrix[i][left];
            matrix[i][left] = matrix[i][right];
            matrix[i][right] = tmp;
            left++;
            right--;
        }
    }
}

复杂度：时间 $O (n^{2})$ （每个元素访问常数次），空间 $O (1)$ （原地操作）。

2.4 变体：逆时针旋转 90°

逆时针旋转 = 先水平翻转（左右翻转），再沿主对角线转置。或者等价于先转置，再上下翻转（垂直翻转）。

// 逆时针旋转 90°：先上下翻转，再转置
// 也可以：先转置，再上下翻转
 
// 上下翻转：交换第 i 行和第 n-1-i 行
for (int i = 0; i < n / 2; i++) {
    int[] tmp = matrix[i];
    matrix[i] = matrix[n - 1 - i];
    matrix[n - 1 - i] = tmp;
}
// 然后转置（同上面代码）

设计哲学：分解复杂变换为简单操作

旋转图像这道题的精妙之处在于：直接实现旋转逻辑需要追踪每个元素的新位置，代码复杂且容易出错。通过分解为”转置 + 翻转”，每步操作都极其简单，且可以原地完成。这种”将复杂操作分解为简单操作的组合”的思想，在算法设计中非常普遍。

第 3 章 LeetCode 73：矩阵置零

3.1 题目

LeetCode 73 - Set Matrix Zeroes（中等）

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

输入:              输出:
[[1,1,1],          [[1,0,1],
 [1,0,1],    →      [0,0,0],
 [1,1,1]]           [1,0,1]]

进阶：

一个直观的解决方案使用 $O (mn)$ 的额外空间（直接复制矩阵）
一个简单的改进方案使用 $O (m + n)$ 的额外空间（记录哪些行/列需要置零）
你能想出一个仅使用常量空间的解决方案吗？

3.2 三种方案的进化

方案一： $O (mn)$ 额外空间

复制整个矩阵，然后根据原矩阵中 0 的位置，在副本中置零。

方案二： $O (m + n)$ 额外空间

用两个数组 zeroRows[m] 和 zeroCols[n] 记录哪些行/列需要置零，然后再次遍历矩阵进行置零。

// O(m+n) 方案
boolean[] zeroRows = new boolean[m];
boolean[] zeroCols = new boolean[n];
// 第一遍：标记需要置零的行和列
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        if (matrix[i][j] == 0) { zeroRows[i] = true; zeroCols[j] = true; }
// 第二遍：置零
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        if (zeroRows[i] || zeroCols[j]) matrix[i][j] = 0;

方案三： $O (1)$ 额外空间——用矩阵的第一行和第一列作为标记

$O (1)$ 方案的核心思路：上面方案二用了额外的 zeroRows 和 zeroCols 数组来标记，能否把这个标记”就地存放”在矩阵本身里？

可以！用第一行当作 zeroCols 的标记，用第一列当作 zeroRows 的标记。matrix[0][j] == 0 表示第 j 列需要置零，matrix[i][0] == 0 表示第 i 行需要置零。

但有一个棘手问题：matrix[0][0] 同时属于第一行和第一列，用它来标记”第一行是否需要置零”还是”第一列是否需要置零”？

解决方案：用 matrix[0][0] 专门标记”第一列是否需要置零”，用一个额外的布尔变量 firstRowZero 记录”第一行是否需要置零”。

3.3 $O (1)$ 方案完整代码

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    
    // 第一步：检查第一行和第一列是否有 0（在修改之前，先记录初始状态）
    boolean firstRowZero = false;
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) { firstRowZero = true; break; }
    }
    // matrix[0][0] 专门负责标记第一列是否需要置零
    boolean firstColZero = false;
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) { firstColZero = true; break; }
    }
    
    // 第二步：用第一行/列作为标记，扫描矩阵内部（[1,1]到[m-1,n-1]）
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0; // 标记第 i 行需要置零
                matrix[0][j] = 0; // 标记第 j 列需要置零
            }
        }
    }
    
    // 第三步：根据标记，置零矩阵内部
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    // 第四步：处理第一行和第一列（根据之前记录的状态）
    if (firstRowZero) {
        for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
    if (firstColZero) {
        for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

为什么要最后处理第一行和第一列？

因为第一行和第一列被用作”标记数组”，如果在置零内部区域之前就把它们置零，会破坏标记信息，导致后续操作出错。必须等内部区域全部处理完后，再根据之前保存的布尔变量处理第一行/列。

复杂度：时间 $O (mn)$ ，空间 $O (1)$ （只用了两个布尔变量）。

第 4 章 LeetCode 36：有效的数独

4.1 题目

LeetCode 36 - Valid Sudoku（中等）

请你判断一个 $9 \times 9$ 的数独是否有效。只需根据以下规则验证已经填入的数字是否有效即可：

数字 1-9 在每一行只能出现一次
数字 1-9 在每一列只能出现一次
数字 1-9 在每一个以粗实线分隔的 $3 \times 3$ 宫内只能出现一次

说明：

一个有效的数独（部分已被填充）不一定是可解的
只需要根据以上规则，验证已经填入的数字是否有效即可
空白格用 '.' 表示

4.2 校验的三个维度

这道题的关键是同时校验三个约束：

行约束：9 行，每行 1-9 不重复
列约束：9 列，每列 1-9 不重复
宫格约束：9 个 $3 \times 3$ 宫格，每格 1-9 不重复

难点在于宫格下标的计算：如何将 $(i, j)$ 映射到其所在的宫格编号？

答案：宫格编号 = (i/3) * 3 + (j/3)

宫格编号（0-8）：
+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

位置 (i=4, j=7): 宫格 = (4/3)*3 + (7/3) = 1*3 + 2 = 5（第5号宫格）✓

4.3 方案一：三个二维布尔数组

最直观的方案：用三个 boolean[9][9] 分别记录每行、每列、每宫格中哪些数字已经出现。

public boolean isValidSudoku(char[][] board) {
    // rows[i][d] = 第 i 行数字 d+1 是否出现
    boolean[][] rows = new boolean[9][9];
    boolean[][] cols = new boolean[9][9];
    boolean[][] boxes = new boolean[9][9];
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            
            int d = board[i][j] - '1'; // 转为 0-indexed（'1'→0，'9'→8）
            int boxIdx = (i / 3) * 3 + (j / 3); // 宫格编号
            
            // 检查是否已存在
            if (rows[i][d] || cols[j][d] || boxes[boxIdx][d]) {
                return false; // 冲突，无效
            }
            
            // 标记已出现
            rows[i][d] = true;
            cols[j][d] = true;
            boxes[boxIdx][d] = true;
        }
    }
    
    return true;
}

复杂度：时间 $O (81) = O (1)$ （棋盘固定为 $9 \times 9$ ，元素总数有上界），空间 $O (27 \times 9) = O (1)$ （固定大小的标记数组）。对于固定规模的问题，复杂度都是 $O (1)$ ，但理解算法时按 $O (n^{2})$ （ $n = 9$ ）思考更有普遍性。

4.4 方案二：位运算压缩（进阶）

用一个 int 的低 9 位来表示 1-9 是否出现：

bit[k] 表示数字 k+1 是否出现
用 (state >> d) & 1 检查数字 d+1 是否出现
用 state |= (1 << d) 标记数字 d+1 出现

public boolean isValidSudoku(char[][] board) {
    int[] rowState = new int[9];  // rowState[i] 的低9位标记第i行的数字
    int[] colState = new int[9];
    int[] boxState = new int[9];
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            
            int d = board[i][j] - '1'; // 0-indexed
            int bit = 1 << d;          // 对应的位掩码
            int boxIdx = (i / 3) * 3 + (j / 3);
            
            // 检查冲突：该位是否已被设置
            if ((rowState[i] & bit) != 0 || 
                (colState[j] & bit) != 0 || 
                (boxState[boxIdx] & bit) != 0) {
                return false;
            }
            
            // 标记出现
            rowState[i] |= bit;
            colState[j] |= bit;
            boxState[boxIdx] |= bit;
        }
    }
    
    return true;
}

位运算版本的空间从 3 × 9 × 9 = 243 个 boolean，压缩到 3 × 9 = 27 个 int。在更大的数独（如 16×16）中，这种压缩的价值更明显。

第 5 章矩阵操作的通用技巧

5.1 宫格坐标计算的推导

很多面试候选人记不住 (i/3)*3 + (j/3) 这个公式。其实不需要死记，理解了就能现场推导：

行方向的宫格编号（0-2）：行号整除 3，i/3
列方向的宫格编号（0-2）：列号整除 3，j/3
把行宫格编号和列宫格编号组合成一个 0-8 的唯一编号：(i/3)*3 + (j/3)（类似二进制的”基 3 表示”）

5.2 矩阵遍历的几种模式

顺序遍历（逐行）：

for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        process(matrix[i][j]);

对角线遍历（主对角线上三角）：

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) // j 从 i+1 开始，跳过对角线本身
        process(i, j);

宫格遍历（数独）：

for (int boxRow = 0; boxRow < 3; boxRow++)      // 宫格行（0-2）
    for (int boxCol = 0; boxCol < 3; boxCol++)  // 宫格列（0-2）
        for (int r = 0; r < 3; r++)             // 宫格内行（0-2）
            for (int c = 0; c < 3; c++)         // 宫格内列（0-2）
                process(boxRow*3+r, boxCol*3+c);

5.3 “先标记后修改”的重要性

Set Matrix Zeroes 的 $O (1)$ 方案中，我们先标记哪些行/列需要置零，然后再统一修改，而不是边扫描边修改。这是矩阵原地修改的通用原则：

如果修改会影响后续扫描的判断，就需要先完成标记再统一执行修改。

这个原则在很多二维数组题中都适用。以 Set Matrix Zeroes 为例，如果扫描到第 $(i, j)$ 个 0 就立刻把整行/列置零，那么后续扫描到的那些”被置零的位置”就无法区分”它本来就是 0”还是”它是被其他 0 置零的”，导致错误地扩大置零范围。

下一篇预告

08 贪心策略：Trapping Rain Water、Gas Station、Candy 将进入贪心算法专题。贪心算法的核心是”每步做局部最优选择，最终得到全局最优结果”——但这个结论需要证明，不是所有问题都能贪心。本篇三道题各有不同的贪心策略：雨水问题用单调栈或双指针，加油站用循环不变量，糖果分发用两遍贪心扫描。

汀的知识碎片

文章导航

07 矩阵数组专题：Rotate Image、Set Matrix Zeroes、Valid Sudoku

矩阵数组专题：Rotate Image、Set Matrix Zeroes、Valid Sudoku

摘要

第 1 章二维数组的坐标变换基础

1.1 矩阵旋转的数学本质

1.2 顺时针 90° = 转置 + 水平翻转

第 2 章 LeetCode 48：旋转图像

2.1 题目

2.2 利用分解的原地算法

2.3 代码实现

2.4 变体：逆时针旋转 90°

第 3 章 LeetCode 73：矩阵置零

3.1 题目

3.2 三种方案的进化

3.3 $O (1)$ 方案完整代码

第 4 章 LeetCode 36：有效的数独

4.1 题目

4.2 校验的三个维度

4.3 方案一：三个二维布尔数组

4.4 方案二：位运算压缩（进阶）

第 5 章矩阵操作的通用技巧

5.1 宫格坐标计算的推导

5.2 矩阵遍历的几种模式

5.3 “先标记后修改”的重要性

下一篇预告

On this page

Backlinks

汀的知识碎片

文章导航

07 矩阵数组专题：Rotate Image、Set Matrix Zeroes、Valid Sudoku

矩阵数组专题：Rotate Image、Set Matrix Zeroes、Valid Sudoku

摘要

第 1 章 二维数组的坐标变换基础

1.1 矩阵旋转的数学本质

1.2 顺时针 90° = 转置 + 水平翻转

第 2 章 LeetCode 48：旋转图像

2.1 题目

2.2 利用分解的原地算法

2.3 代码实现

2.4 变体：逆时针旋转 90°

第 3 章 LeetCode 73：矩阵置零

3.1 题目

3.2 三种方案的进化

3.3 O(1) 方案完整代码

第 4 章 LeetCode 36：有效的数独

4.1 题目

4.2 校验的三个维度

4.3 方案一：三个二维布尔数组

4.4 方案二：位运算压缩（进阶）

第 5 章 矩阵操作的通用技巧

5.1 宫格坐标计算的推导

5.2 矩阵遍历的几种模式

5.3 “先标记后修改”的重要性

下一篇预告

On this page

Backlinks

第 1 章二维数组的坐标变换基础

3.3 $O (1)$ 方案完整代码

第 5 章矩阵操作的通用技巧