73.md

73. Set Matrix Zeroes

题目链接

public class Solution {
	
	public void setZeroes(int[][] matrix) {
		HashSet<Integer> row = new HashSet<>();
		HashSet<Integer> column = new HashSet<>();
		int high = matrix.length;
		int width = matrix[0].length;
		for(int i = 0; i < matrix.length ; i++){
			for(int j = 0;j < matrix[i].length; j++){
				if(matrix[i][j] == 0){
					row.add(i);
					column.add(j);
				}
			}
		}
		
		Iterator<Integer> rIt = row.iterator();
		Iterator<Integer> cIt = column.iterator();
		while (rIt.hasNext()) {
			int col = rIt.next();
			for(int i = 0; i < width; i++){
				matrix[col][i] = 0;
			}
		}
		while (cIt.hasNext()) {
			int ro = cIt.next();
			for(int i = 0; i < high; i++){
				matrix[i][ro] = 0;
			}
		}
	}
}

上面代码的思路是首先遍历一边数组，然后将0元素的位置记录下来。然后再进行两次循环分别将对应的行或列至为0，时间复杂度为$O(n*m)$,空间复杂度为$O(n+m)$?。

一个空间复杂的为$O(1)$的算法

void setZeroes(vector<vector<int> > &matrix) {
    int col0 = 1, rows = matrix.size(), cols = matrix[0].size();

    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) col0 = 0;
        for (int j = 1; j < cols; j++)
            if (matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
    }

    for (int i = rows - 1; i >= 0; i--) {
        for (int j = cols - 1; j >= 1; j--)
            if (matrix[i][0] == 0 || matrix[0][j] == 0)
                matrix[i][j] = 0;
        if (col0 == 0) matrix[i][0] = 0;
    }
}

该算法的思路是：遍历矩阵，如果其中有一个元素为0，那么将该行的第一个元素和该列的第一个元素至为0，也就是将遍历的结果存储在矩阵的第一行和第一列中。但是矩阵的第一个元素既是第一行也是第一列，所以还需要一个额外的空间来存储，这就是唯一的存储空间的作用。