Sign in Subscribe
算法

矩阵置零

loser

• 7 min read
Share

给定一个 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]]

提示：

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

进阶：

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

解法一（行列标记数组）：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<bool> row(m, false);
        vector<bool> col(n, false);

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == 0)
                {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (row[i] || col[j])
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

解法二（第一行第一列作为标记）：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        bool firstRowZero = false;
        bool firstColZero = false;

        for (int j = 0; j < n; j++)
        {
            if (matrix[0][j] == 0)
            {
                firstRowZero = true;
                break;
            }
        }

        for (int i = 0; i < m; i++)
        {
            if (matrix[i][0] == 0)
            {
                firstColZero = true;
                break;
            }
        }

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (matrix[i][j] == 0)
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        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;
            }
        }
    }
};

核心思想

题目要求：只要矩阵中某个位置 matrix[i][j] 是 0，就要把第 i 行和第 j 列都变成 0。

最容易想到的是，先记录哪些行、哪些列需要置零。

然后第二次遍历矩阵：

  • 如果当前位置所在行需要置零，就把它设为 0
  • 如果当前位置所在列需要置零，也把它设为 0

关键点是：不能在第一次扫描时直接把行列改成 0。

因为新改出来的 0 会干扰后续判断，让本来不该置零的行列也被置零。

所以必须先“记录原始的 0 所在行列”，再统一修改矩阵。

解法一：行列标记数组

使用两个标记数组：

vector<bool> row(m, false);
vector<bool> col(n, false);

含义是：

  • row[i] == true：第 i 行需要置零
  • col[j] == true：第 j 列需要置零

第一次遍历矩阵时，如果发现：

matrix[i][j] == 0

就标记：

row[i] = true;
col[j] = true;

第二次遍历时，如果：

row[i] || col[j]

说明当前位置所在行或者所在列需要置零，于是：

matrix[i][j] = 0;

这个方法简单清晰，空间复杂度是 O(m + n)。

解法二：第一行第一列作为标记

进阶要求使用常量空间。

我们可以不额外开 row 和 col 数组，而是直接利用矩阵的第一行和第一列当作标记区。

具体来说：

  • 用 matrix[i][0] 标记第 i 行是否需要置零
  • 用 matrix[0][j] 标记第 j 列是否需要置零

如果在内部区域发现：

matrix[i][j] == 0

就设置：

matrix[i][0] = 0;
matrix[0][j] = 0;

这样就把“第 i 行需要置零”和“第 j 列需要置零”的信息存到了原矩阵中。

为什么第一行和第一列要单独记录

第一行和第一列比较特殊。

因为它们既是原始数据，又被我们拿来当标记区。

例如 matrix[0][j] 有两种含义：

  1. 它原本就是第一行中的一个元素。
  2. 它后来也可能被用来标记第 j 列是否需要置零。

如果不提前记录第一行本身是否需要置零，后面就分不清：

第一行里的 0 是原本就有的，还是后面作为列标记写进去的。

所以需要两个变量：

bool firstRowZero = false;
bool firstColZero = false;

分别记录：

  • 原始第一行是否包含 0
  • 原始第一列是否包含 0

这两个变量必须在使用第一行第一列做标记之前先算出来。

为什么内部区域从 (1, 1) 开始

常量空间解法中，第一行和第一列作为标记区。

因此在标记阶段，只扫描内部区域：

i = 1 ... m - 1

j = 1 ... n - 1

如果内部某个位置为 0，就把对应行首和列首置为 0。

之后再根据第一行和第一列的标记，去修改内部区域。

最后再根据 firstRowZero 和 firstColZero，决定是否把第一行、第一列置零。

这个顺序不能反。

如果一开始就把第一行或第一列置零，那么标记信息会被破坏，内部区域也会被错误影响。

正确性证明

我们证明常量空间解法可以正确完成矩阵置零。

结论 1：第一行和第一列的原始置零需求被正确保存

算法在修改任何标记之前，先扫描原始第一行和第一列。

如果第一行中存在 0，就令：

firstRowZero = true

如果第一列中存在 0，就令：

firstColZero = true

因此，第一行和第一列是否需要置零的信息不会因为后续标记操作而丢失。

结论 2：内部区域的置零需求被正确记录

对于任意内部位置：

matrix[i][j]

其中：

i >= 1

j >= 1

如果它原本是 0，算法会执行：

matrix[i][0] = 0;
matrix[0][j] = 0;

这表示第 i 行和第 j 列需要置零。

所以所有由内部原始 0 引起的行列置零需求都会被记录下来。

结论 3：内部区域会被正确置零

第二次扫描内部区域时，算法检查：

matrix[i][0] == 0 || matrix[0][j] == 0

如果第 i 行需要置零，或者第 j 列需要置零，那么当前位置就应该变成 0。

这正好对应题目要求。

如果这两个标记都不是 0，说明当前行和当前列都没有原始 0 触发置零，当前位置应该保持原值。

因此内部区域被正确处理。

结论 4：第一行和第一列会被正确置零

内部区域处理完以后，算法最后根据：

firstRowZero

决定是否把第一行全部置零。

根据：

firstColZero

决定是否把第一列全部置零。

由于这两个变量保存的是原始第一行和第一列的信息，所以第一行、第一列也会被正确处理。

得出结论

由结论 1 可知，第一行和第一列的原始信息不会丢失。

由结论 2 可知，所有内部原始 0 的影响都会被记录。

由结论 3 可知，内部区域会按照标记正确置零。

由结论 4 可知，第一行和第一列会被正确置零。

所以整个矩阵最终结果正确。

举例理解

以：

matrix = [[1,1,1],
          [1,0,1],
          [1,1,1]]

为例。

第一行没有 0：

firstRowZero = false

第一列没有 0：

firstColZero = false

扫描内部区域时，发现：

matrix[1][1] == 0

于是标记：

matrix[1][0] = 0;
matrix[0][1] = 0;

矩阵变成：

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

然后根据第一行第一列的标记处理内部区域：

  • 第 1 行需要置零
  • 第 1 列需要置零

最终得到：

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

复杂度分析

解法一

  • 扫描矩阵两次
  • 时间复杂度：O(mn)
  • 使用两个标记数组
  • 空间复杂度：O(m + n)

解法二

  • 扫描第一行、第一列和矩阵内部
  • 整体仍然是常数次遍历矩阵
  • 时间复杂度：O(mn)
  • 只使用两个布尔变量
  • 空间复杂度：O(1)

如果按照进阶要求，推荐使用解法二。