【LeetCode】No.73. Set Matrix Zeroes -- Java Version

题目链接：https://leetcode.com/problems/set-matrix-zeroes/

1. 题目介绍（Set Matrix Zeroes）

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

【Translate】： 给定一个m × n的整数矩阵matrix，如果其中某一个元素是0，那么请将它的整行和整列都设置为0。

You must do it in place.

【Translate】： 在原矩阵上执行。

【测试用例】：

【条件约束】：

【跟踪】：

【Translate】：

• 使用O(mn)空间的直接解决方案可能不是一个好主意。
• 一个简单的改进使用O(m + n)空间，但仍然不是最好的解决方案。
• 你能设计一个常数空间解吗？

2. 题解

2.1 常规思路（Map存储 + 循环嵌套）

感觉这个思路就是很常规的思路，没有优化，只为了解题。首先一开始简单粗暴，遍历二维数组matrix，通过Map>的方式记录元素为0的位置，List记录的当前行的列下标。一轮循环记录完毕后，我们开始遍历map，并判断list里是否有值，因为上一步循环中会记录所有的行下标（这个地方就有些重复，最好改成该行有0才记录该行行号），最后就是行列的赋0操作。

// O(m+n) space.?
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        Map<Integer,List<Integer>> map = new HashMap<>();
        // 遍历matrix，记录元素为0的位置
        for(int i = 0; i < m; i++){
            ArrayList<Integer> list = new ArrayList<>();
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    list.add(j);
                }
            }
            map.put(i,list);
        }
        
        for(Integer key:map.keySet()){
            List<Integer> value = map.get(key);
            if(value.size() > 0){
                for(int i = 0; i < n; i++){
                    matrix[key][i] = 0;
                }
                
                for (int j = 0; j < value.size(); j++) {
                    // System.out.println("map = " + value.get(1));
                    for(int x = 0; x < m; x++){
                        matrix[x][value.get(j)] = 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

2.2 行首标记

原题解来自于dietpepsi的Java/Python O(1) space 11 lines solution。该题解首先通过一个while循环检查了第一行是否存在0元素，然后从第2行开始遍历所有元素，检查是否存在0元素，如果存在就将该元素对应的行首和列首置为0；随后反向检查元素，如果该元素的行首或列首有一项为0，那么就将该元素置为0；最后根据一开始while循环结果判断第一行是否存在0元素，如果存在，则将第一行全部置为0.

// O(1) space.?
public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, k = 0;
    // First row has zero?
    while (k < n && matrix[0][k] != 0) ++k;
    // Use first row/column as marker, scan the matrix
    for (int i = 1; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (matrix[i][j] == 0)
                matrix[0][j] = matrix[i][0] = 0;
    // Set the zeros
    for (int i = 1; i < m; ++i)
        for (int j = n - 1; j >= 0; --j)
            if (matrix[0][j] == 0 || matrix[i][0] == 0)
                matrix[i][j] = 0;
    // Set the zeros for the first row
    if (k < n) Arrays.fill(matrix[0], 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.3 辅助数组标记

原题解来自于KnightY的My JAVA solution, easy to understand。该题解的思想确实和标题一样，易于理解，KnightY使用了行列两个辅助数组，通过一次遍历，记录下行列位置，之后再遍历一遍，如果行或列数组中该位置有标记，那么就将该元素置为0.

// O(m+n) space.
class Solution {
    public void setZeroes(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int[] row = new int[m];
        int[] col = new int[n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==0){
                    row[i]=1;
                    col[j]=1;
                }
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(row[i]==1||col[j]==1){
                    matrix[i][j]=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

3. 参考资料

[1] Arrays.fill()的用法 | CSDN