矩阵置零

发表于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

LeetCode每日一题，73. Set Matrix Zeros

先看题目描述

64gTET.png

大意就是给定一个矩阵，若矩阵中某个元素为 0，则将该行和该列的所有元素都置为 0

算法和思路

标记数组

这是 O(m + n) 的空间复杂度的解法，思路就是使用两个布尔数组 rows 和 cols，记录某行或某列是否需要翻转。遍历数组 matrix 的所有元素，遍历到 matrix[i][j] 时，若值为 0，则令 rows[i] 为 true，cols[j] 为 true，遍历完 matrix 后，再去遍历 rows 和 cols 数组，若值为 true，则将相应行或相应列全置 0

算法源码

标记数组

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
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] rows = new boolean[m];
        boolean[] cols = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            if (rows[i]) {
                Arrays.fill(matrix[i], 0);
            }
        }
        for (int j = 0; j < n; j++) {
            if (cols[j]) {
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

使用两个标记变量

这是空间复杂度为 O(1) 的解法，思路就是使用两个标记变量分别记录第 0 行和第 0 列是否包含 0。遍历除了第 0 行和第 0 列外的其他所有元素，遍历到 matrix[i][j] 时，若值为 0，则令 matrix[i][0] 和 matrix[0][j] 为 0，代表第 i 行和第 i 列均需要被置 0。然后遍历第 0 行和第 0 列的元素，遍历到值为 0 的元素时则将对应行或列置 0，最后通过两个标记变量将第 0 行或第 0 列置 0

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
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean rowFlag = false;
        boolean colFlag = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                colFlag = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                rowFlag = 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++) {
            if (matrix[i][0] == 0) {
                Arrays.fill(matrix[i], 0);
            }
        }
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowFlag) {
            Arrays.fill(matrix[0], 0);
        }
        if (colFlag) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}