Vault 101

xjay2007's Blog

0%

LeetCode 73. 矩阵置零

发表于 更新于 分类于 ， Valine：

题目描述

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 
[
  [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) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个常数空间的解决方案吗？

题解

题目乍看比较简单，但是比较坑的地方在于原地修改，修改时需要记录原本是0的元素。

额外空间

空间复杂度 $O(M \times N)$

思路
  • 遍历所有节点，如果 matrix[i][j] 为 0 ，则将所在行 i 与列 j 的所有元素置为 0 。
  • 记录一个二维数组 visited[][]，表示这个节点是否访问过。
  • 置 0 过程中，将访问数组 visited[i][j] 记录为 true 。如果原本值已经为 0 ，则记录为 false ，以便下次可以扫描到。
复杂度
  • 时间复杂度：$O((M \times N) \times (M+N))$
  • 空间复杂度：$O(M \times N)$
代码
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
// C++
void setZeroes(vector<vector<int>>& matrix) {
    int R = (int)matrix.size();
    int C = (int)matrix[0].size();
    vector<vector<bool>> visited(R, vector<bool>(C, false));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (visited[i][j]) {
                continue;
            }
            if (matrix[i][j] == 0) {
                for (int k = 0; k < R; ++k) {
                    if (visited[k][j]) {
                        continue;
                    }
                    visited[k][j] = (matrix[k][j] != 0);
                    matrix[k][j] = 0;
                }
                for (int l = 0; l < C; ++l) {
                    if (visited[i][l]) {
                        continue;
                    }
                    visited[i][l] = (matrix[i][l] != 0);
                    matrix[i][l] = 0;
                }
            }
        }
    }
}

空间复杂度 $O(M+N)$

思路
  • 第一次遍历所有元素，使用 zeroRows[M] 和 zeroCols[N] 来记录哪些行和列有 0 元素存在。
  • 第二次遍历根据记录，如果 zeroRows[i] == true || zeroCols[j] == true ，则将 matrix[i][j] 置为 0 。
复杂度
  • 时间复杂度：$O(M \times N)$
  • 空间复杂度：$O(M + N)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// C++
void setZeroes(vector<vector<int>>& matrix) {
    int R = (int)matrix.size();
    int C = (int)matrix[0].size();
    vector<bool> zeroRows(R, false);
    vector<bool> zeroCols(C, false);
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (matrix[i][j] == 0) {
                zeroRows[i] = true;
                zeroCols[j] = true;
            }
        }
    }
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (zeroRows[i] || zeroCols[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

暴力法 空间复杂度 $O(1)$

思路

  • 第一次遍历，如果 matrix[i][j] 为 0 ，则修改所在行 i 与列 j 的所有元素，将所有非 0 元素置为一个特殊值 MODIFED = -1000000 ，说明该位置的元素被修改过。
  • 第二次遍历，如果 matrix[i][j] == MODIFIED ，则将其置为 0 。

复杂度

  • 时间复杂度：$O((M \times N) \times (M + N))$
  • 空间复杂度：$O(1)$

代码

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
// C++
void setZeroes(vector<vector<int>>& matrix) {
    int R = (int)matrix.size();
    int C = (int)matrix[0].size();
    int MODIFIED = -1000000;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (matrix[i][j] == 0) {
                for (int k = 0; k < R; ++k) {
                    if (matrix[k][j] != 0) {
                        matrix[k][j] = MODIFIED;
                    }
                }
                for (int l = 0; l < C; ++l) {
                    if (matrix[i][l] != 0) {
                        matrix[i][l] = MODIFIED;
                    }
                }
            }
        }
    }
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (matrix[i][j] == MODIFIED) {
                matrix[i][j] = 0;
            }
        }
    }
}

改进方案 空间复杂度 $O(1)$

算法

  1. 遍历整个矩阵，将矩阵的第一行和第一列的所有元素做为标志位，代表这行或这列需要置为 0 。
1
2
3
4
if matrix[i][j] == 0 {
    matrix[i][0] = 0;
    matrix[0][j] = 0;
}

  1. 由于第一行与第一列被用作标志位，所以需要额外的变量标记第一行与第一列， isCol 记录第一列是否需要置 0 ，matrix[0][0] 则用来标记第一行是否需要置 0 。

  2. 从第二行与第二列即 matrix[1][1] 开始遍历

    1
    2
    3
    if matrix[i][0] == 0 || matrix[i][1] == 0 {
        matrix[i][j] = 0;
    }

  3. 如果 matrix[0][0] == 0 ，则第一行置为 0 。

  4. 如果 isCol == true ，则第一列置为 0 。

复杂度

  • 时间复杂度：$O(M \times N)$
  • 空间复杂度：$O(1)$

代码

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
// C++
void setZeroes(vector<vector<int>>& matrix) {
    int R = (int)matrix.size();
    int C = (int)matrix[0].size();
    bool isCol = true;
    for (int i = 0; i < R; ++i) {
        if (matrix[i][0] == 0) {
            isCol = true;
        }
        for (int j = 1; j < C; ++j) {
            if (matrix[i][j] == 0) {
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
    for (int i = 1; i < R; ++i) {
        for (int j = 1; j < C; ++j) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if (matrix[0][0] == 0) {
        for (int j = 1; j < C; ++j) {
            matrix[0][j] = 0;
        }
    }
    if (isCol) {
        for (int i = 0; i < R; ++i) {
            matrix[i][0] = 0;
        }
    }
}

参考链接

相似文章