矩阵置零

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：数组、矩阵、原地算法

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

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

进阶：

• 一个直观的解决方案是使用 $O(mn)$ 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 $O(m + n)$ 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

---

2. 解题思路拆解

方法：使用首行首列作为标记位

为了达到 $O(1)$ 的空间复杂度，我们需要利用矩阵本身来存储标记信息。 我们可以使用第一行和第一列来记录某一行或某一列是否需要置零。

1. 预处理标记：

   • 首先，我们需要两个布尔变量 row0 和 col0，分别记录第一行本身和第一列本身是否包含 0。因为稍后我们会用第一行第一列存状态，会覆盖掉它们原本的信息。
   • col0：如果第一列中有 0，col0 = true。
   • row0：如果第一行中有 0，row0 = true。

2. 利用首行首列存储状态：

   • 遍历矩阵的其他元素（从 (1, 1) 开始）。
   • 如果 matrix[i][j] === 0，则将它对应的行首 matrix[i][0] 和列首 matrix[0][j] 置为 0。

3. 根据标记置零：

   • 再次遍历矩阵（从 (1, 1) 开始）。
   • 如果某元素对应的行首 matrix[i][0] === 0 或者列首 matrix[0][j] === 0，则将 matrix[i][j] 置为 0。

4. 处理首行首列：

   • 最后，根据 row0 和 col0 的值，决定是否将第一行和第一列全置为 0。

---

3. 代码实现

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    let row0 = false;
    let col0 = false;
    
    // 1. 检查第一列是否有 0
    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) {
            col0 = true;
            break;
        }
    }
    
    // 2. 检查第一行是否有 0
    for (let j = 0; j < n; j++) {
        if (matrix[0][j] === 0) {
            row0 = true;
            break;
        }
    }
    
    // 3. 使用第一行和第一列记录其他行列的状态
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    
    // 4. 根据第一行和第一列的标记，置零其他元素
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    // 5. 处理第一行和第一列
    if (row0) {
        for (let j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }
    
    if (col0) {
        for (let i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
};

代码执行演示

输入 matrix = [[1,1,1],[1,0,1],[1,1,1]]

1. 检查首行首列：
   • col0: false (第一列全是1)
   • row0: false (第一行全是1)
2. 标记：
   • 遍历 (1,1)，发现是 0。
   • 设置 matrix[1][0] = 0 (第二行行首)
   • 设置 matrix[0][1] = 0 (第二列列首)
   • 此时矩阵：

     [1, 0, 1]
     [0, 0, 1]
     [1, 1, 1]

3. 置零：
   • 遍历 (1,0) 到 (2,2) (除了首行首列的区域)。
   • i=1: matrix[1][0] 是 0，所以整行 matrix[1][...] 都要变 0。matrix[1][1]=0, matrix[1][2]=0。
   • i=2:
     • j=1: matrix[0][1] 是 0，所以 matrix[2][1]=0。
   • 此时矩阵：

     [1, 0, 1]
     [0, 0, 0]
     [1, 0, 1]

4. 处理首行首列：
   • row0 是 false，第一行保持原样。
   • col0 是 false，第一列保持原样。
   • 最终结果：

     [1, 0, 1]
     [0, 0, 0]
     [1, 0, 1]

   • 等等，演示里的 matrix[0][1] 被标记改成了 0，这会不会影响最后一步？
   • 关键点：步骤 4 的遍历是从 i=1, j=1 开始的，不会覆盖第一行第一列。第一行第一列的最终状态由 row0 和 col0 决定。这里 matrix[0][1] 变成了 0 是因为它作为标记位确实需要变成 0，它同时也代表这列最终要是 0。所以结果是正确的。

---

4. 复杂度分析

维度	描述
时间复杂度	$O(mn)$。我们需要遍历矩阵几次，但总次数是常数级别的。
空间复杂度	$O(1)$。只使用了两个布尔变量。