Set Matrix Zeros

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

Do it in place.

Given array A as

1 0 1
1 1 1 
1 1 1

On returning, the array A should be :

0 0 0
1 0 1
1 0 1

思路:

用两个array/set记录需要归零的row和column。

Solution:

Time: O(m*n)
Space: O(max(m, n))

public class Solution {
    public void setZeroes(ArrayList<ArrayList<Integer>> a) {
        int m = a.size();
        int n = a.get(0).size();
        ArrayList<Boolean> row = new ArrayList<>(m);
        for (int i = 0; i < m; i ++) {
            row.add(false);
        }
        ArrayList<Boolean> col = new ArrayList<>(n);
        for (int j = 0; j < n; j ++) {
            col.add(false);
        }
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (a.get(i).get(j) == 0) {
                    row.set(i, true);
                    col.set(j, true);
                }
            }
        }
        for (int i = 0; i < m; i ++) {
            if (row.get(i)) {
                for (int j = 0; j < n; j ++) {
                    a.get(i).set(j, 0);
                }
            }
        }
        for (int j = 0; j < n; j ++) {
            if (col.get(j)) {
                for (int i = 0; i < m; i ++) {
                    a.get(i).set(j, 0);
                }
            }
        }
    }
}