setMatrixZeroes

73. 矩阵置零

分析

标记行和列：
- 用第一行和第一列作为标记位置
- 如果矩阵中的元素 matrix[i][j] == 0，则将 matrix[i][0] 和 matrix[0][j] 置为 0 ，分别标记第 i 行和第 j 列需要被置 0
特殊处理首行和首列：
- 因为第一行和第一列被用作标记，置 0 的操作可能覆盖原始信息
- 使用两个额外变量 r 和 c 分别标记首行和首列是否需要置 0
置零操作：
- 根据第一列的标记，从第二行开始，将需要置 0 的行的所有元素置为 0
- 根据第一行的标记，从第二列开始，将需要置 0 的列的所有元素置为 0
处理首行和首列：
- 如果 r == 0，将第一行全部置 0
- 如果 c == 0，将第一列全部置 0

时间复杂度

时间复杂度：O(m * n)

空间复杂度

使用矩阵本身作为标记，无额外空间开销，空间复杂度为 O(1)

C++代码

 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


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

        // 标记需要置零的行和列
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (matrix[i][j] == 0)
                {
                    if (i == 0) r = 0;
                    if (j == 0) c = 0;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }

        // 根据标记置零
        for (int i = 1; i < n; ++i)
            if (matrix[i][0] == 0)
                for (int j = 1; j < m; ++j)
                    matrix[i][j] = 0;

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

        // 处理首行和首列
        if (r == 0)
            for (int j = 0; j < m; ++j)
                matrix[0][j] = 0;

        if (c == 0)
            for (int i = 0; i < n; ++i)
                matrix[i][0] = 0;
    }
};