📝 题目描述

题目链接：矩阵置零

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

示例：

示例 1：

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

示例 2：

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

💡 解题思路

方法一：标记数组

首先我们创建两个bool数组zero_row(m), zero_col(n)，分别代表矩阵的m行和n列。

该bool数组的含义是：如果zero_row[i] = true，那么代表矩阵的第i行需要全置为0；同理如果zero_col[j] = true，那么代表矩阵的第j列需要全置为0。

因此，首先我们需要先扫描一遍矩阵，找到0元素的位置，然后将其所在的行和列使用标记数组标为true。

然后我们再次遍历矩阵，对于矩阵的位置(i, j)，如果zero_row[i] = true或者zero_col[j] = true，那么该位置就需要改为0。

方法二：使用两个标记变量

我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。

在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

🔧 代码实现

1、标记数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> zero_row(m), zero_col(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zero_row[i] = zero_col[j] = true;
                }
            }
        }

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

2、使用两个标记变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // 预先设置两个变量，分别代表第一行是否需要置0、第一列是否需要置0
        bool flag_row0 = false, flag_col0 = false;

        // 遍历第一行，检查是否有零元素
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                flag_row0 = true;
            }
        }

        // 遍历第一列，检查是否有零元素
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flag_col0 = true;
            }
        }

        // 遍历矩阵，令第一行、第一列作为标记
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        // 遍历矩阵，置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 (flag_row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // 根据标记情况，为第一列置零
        if (flag_col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

📊 复杂度分析

1、标记数组

  • 时间复杂度：O(mn)O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
  • 空间复杂度：O(m+n)O(m + n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。

2、使用两个标记变量

  • 时间复杂度：O(mn)O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
  • 空间复杂度：O(1)O(1)。我们只需要常数空间存储若干变量。

🎯 总结

  • 核心思想：想起来使用标记数组。