leetcode-set-matrix-zeros

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/set-matrix-zeroes/

　　给你一个矩阵，如果矩阵中某个值为0，那么把该行该列值全部赋值为0

题目分析

　　题目想让你用额外的O(1)空间复杂度去做，一个巧妙的方法是先遍历矩阵，如果某个值为0，则把此值相同列的第一行元素赋值为0，同时把相同行的第一列元素赋值为0，然后最后做统一的set。但是第一行和第一列的值会被修改，导致不知道第一行或者第一列本来有没有0的元素，因此首先先记下第一行和第一列是否有0元素。在set 0的时候先从第二行，第二列开始set。最后处理第一行和第一列。

代码

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
public class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        boolean b1 = false;
        boolean b2 = false;
        for(int i = 0; i < row; i++) {
            if(matrix[i][0] == 0) {
                b1 = true;
            }
        }
        for(int j = 0; j < col; j++) {
            if(matrix[0][j] == 0) {
                b2 = true;
            }
        }
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1; i < row; i++) {
            if(matrix[i][0] == 0) {
                for(int j = 1; j < col; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for(int j = 1; j < col; j++) {
            if(matrix[0][j] == 0) {
                for(int i = 1; i < row; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if(b1) {
            for(int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
        if(b2) {
            for(int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

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