lc73矩阵置零——尽可能减少空间复杂度

73. 矩阵置零 - 力扣（LeetCode）

法1：

很容易想到，O(m+n)空间复杂度，记录哪些行，哪些列有0。

法2：

常量空间，第一次做不太好想到。法1是用额外数组记录行列的0情况，法2优化为 用原矩阵的，第一列记录每行有0的情况，第一行用于记录每列有0的情况。而对于第一行和第一列本身就有0的情况，额外拿2个变量（常量）记录，有的话，把其置位0.

注意第二次遍历，从1,1开始，要忽略第一行和第一列。

class Solution {public void setZeroes(int[][] matrix) {boolean rowExist = false;boolean colExist = false;int m = matrix.length;int n = matrix[0].length;      //第一次遍历，统计for(int i = 0;i<m;i++) {for(int j=0; j<n; j++) {if(matrix[i][j] == 0) {if(i == 0)rowExist = true;if(j == 0)colExist = true;matrix[i][0] = 0;matrix[0][j] = 0;}}}//第二次遍历变0for(int i = 1;i<m;i++) {for(int j=1; j<n; j++) {if(matrix[i][0] == 0 || matrix[0][j] == 0)matrix[i][j] = 0;}}//是否第一行和第一列原本就有0if(rowExist) {for(int i = 0;i<n;i++)matrix[0][i] = 0;}if(colExist) {for(int i=0;i<m;i++)matrix[i][0]=0;}}
}

当然也可进一步优化，只用一个m[0][0]标记第1行有无0，再额外用一个变量记录第一列有无0即可。