題目描述（中等難度）
給定一個矩陣信粮，然后找到所有含有 0 的地方姨俩，把該位置所在行所在列的元素全部變成 0匆赃。
解法一
暴力解法鸟赫，用一個等大的空間把給定的矩陣存起來蒜胖，然后遍歷這個矩陣，遇到 0 就把原矩陣的當(dāng)前行抛蚤，當(dāng)前列全部變作 0台谢，然后繼續(xù)遍歷。
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
int[][] matrix_copy = new int[row][col];
//復(fù)制矩陣
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
matrix_copy[i][j] = matrix[i][j];
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//找到 0 的位置
if (matrix_copy[i][j] == 0) {
//將當(dāng)前行岁经，當(dāng)前列置為 0
setRowZeroes(matrix, i);
setColZeroes(matrix, j);
}
}
}
}
//第 col 列全部置為 0
private void setColZeroes(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
//第 rol 行全部置為 0
private void setRowZeroes(int[][] matrix, int row) {
for (int i = 0; i < matrix[row].length; i++) {
matrix[row][i] = 0;
}
}
時間復(fù)雜度：O ( mn )朋沮。
空間復(fù)雜度：O（mn）。m 和 n 分別是矩陣的行數(shù)和列數(shù)蒿偎。
解法二
空間復(fù)雜度可以優(yōu)化一下朽们，我們可以把哪一行有 0 ，哪一列有 0 都記錄下來诉位，然后最后統(tǒng)一把這些行骑脱，這些列置為 0。
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
//用兩個 bool 數(shù)組標(biāo)記當(dāng)前行和當(dāng)前列是否需要置為 0
boolean[] row_zero = new boolean[row];
boolean[] col_zero = new boolean[col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//找到 0 的位置
if (matrix[i][j] == 0) {
row_zero[i] = true;
col_zero[j] = true;
}
}
}
//將行標(biāo)記為 true 的行全部置為 0
for (int i = 0; i < row; i++) {
if (row_zero[i]) {
setRowZeroes(matrix, i);
}
}
//將列標(biāo)記為 false 的列全部置為 0
for (int i = 0; i < col; i++) {
if (col_zero[i]) {
setColZeroes(matrix, i);
}
}
}
//第 col 列全部置為 0
private void setColZeroes(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
//第 rol 行全部置為 0
private void setRowZeroes(int[][] matrix, int row) {
for (int i = 0; i < matrix[row].length; i++) {
matrix[row][i] = 0;
}
}
時間復(fù)雜度：O ( mn )苍糠。
空間復(fù)雜度：O（m + n）叁丧。m 和 n 分別是矩陣的行數(shù)和列數(shù)。
順便說一下 leetcode 解法一說的解法岳瞭，思想是一樣的拥娄，只不過它沒有用 bool 數(shù)組去標(biāo)記，而是用兩個 set 去存行和列瞳筏。
class Solution {
public void setZeroes(int[][] matrix) {
int R = matrix.length;
int C = matrix[0].length;
Set<Integer> rows = new HashSet<Integer>();
Set<Integer> cols = new HashSet<Integer>();
// 將元素為 0 的地方的行和列存起來
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (matrix[i][j] == 0) {
rows.add(i);
cols.add(j);
}
}
}
//將存儲的 Set 拿出來稚瘾，然后將當(dāng)前行和列相應(yīng)的元素置零
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (rows.contains(i) || cols.contains(j)) {
matrix[i][j] = 0;
}
}
}
}
}
這里，有一個比自己巧妙的地方時姚炕，自己比較直接的用兩個函數(shù)去將行和列分別置零摊欠，但很明顯自己的算法會使得一些元素重復(fù)置零。而上邊提供的算法柱宦，每個元素只遍歷一次就夠了些椒，很棒。
解法三
繼續(xù)優(yōu)化空間復(fù)雜度掸刊，接下來用的思想之前也用過免糕，例如41題解法二和47題解法二，就是用給定的數(shù)組去存我們需要的數(shù)據(jù)，只要保證原來的數(shù)據(jù)不丟失就可以石窑。
按 47題解法二 的思路牌芋，就是假設(shè)我們對問題足夠的了解，假設(shè)存在一個數(shù)尼斧，矩陣中永遠(yuǎn)不會存在姜贡，然后我們就可以把需要變成 0 的位置先變成這個數(shù)，也就是先標(biāo)記一下棺棵，最后再統(tǒng)一把這個數(shù)變成 0楼咳。直接貼下leetcode解法二的代碼。
class Solution {
public void setZeroes(int[][] matrix) {
int MODIFIED = -1000000; //假設(shè)這個數(shù)字不存在于矩陣中
int R = matrix.length;
int C = matrix[0].length;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
//找到等于 0 的位置
if (matrix[r][c] == 0) {
// 將需要變成 0 的行和列改為之前定義的數(shù)字
// 如果是 0 不要管烛恤，因為我們要找 0 的位置
for (int k = 0; k < C; k++) {
if (matrix[r][k] != 0) {
matrix[r][k] = MODIFIED;
}
}
for (int k = 0; k < R; k++) {
if (matrix[k][c] != 0) {
matrix[k][c] = MODIFIED;
}
}
}
}
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
// 將是定義的數(shù)字的位置變成 0
if (matrix[r][c] == MODIFIED) {
matrix[r][c] = 0;
}
}
}
}
}
時間復(fù)雜度：O ( mn )母怜。
空間復(fù)雜度：O（1）。m 和 n 分別是矩陣的行數(shù)和列數(shù)缚柏。
當(dāng)然苹熏，這個解法局限性很強(qiáng)，很依賴于樣例的取值币喧，我們繼續(xù)想其他的方法轨域。
回想一下解法二，我們用了兩個 bool 數(shù)組去標(biāo)記當(dāng)前哪些行和那些列需要置零杀餐，我們能不能在矩陣中找點兒空間去存我們的標(biāo)記呢干发？
可以的！因為當(dāng)我們找到第一個 0 的時候史翘，這個 0 所在行和所在列就要全部更新成 0枉长，所以它之前的數(shù)據(jù)是什么就不重要了，所以我們可以把這一行和這一列當(dāng)做標(biāo)記位琼讽，0 當(dāng)做 false必峰，1 當(dāng)做 true，最后像解法二一樣钻蹬，統(tǒng)一更新就夠了吼蚁。
如上圖，找到第一個 0 出現(xiàn)的位置问欠，把橙色當(dāng)做解法二的列標(biāo)志位肝匆，黃色當(dāng)做解法二的行標(biāo)志位。
如上圖溅潜，我們首先需要初始化為 0，并且遇到之前是 0 的位置我們需要把它置為 1薪伏，代表當(dāng)前行（或者列）最終要值為 0滚澜。
如上圖，繼續(xù)遍歷找 0 的位置嫁怀，找到后將對應(yīng)的位置置為 1 即可设捐。橙色部分的數(shù)字為 1 代表當(dāng)前列要置為 0借浊，黃色部分的數(shù)字為 1 代表當(dāng)前行要置為 0。
看下代碼吧萝招。
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
int free_row = -1; //記錄第一個 0 出現(xiàn)的行
int free_col = -1; //記錄第一個 0 出現(xiàn)的列
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//如果是當(dāng)前作為標(biāo)記的列蚂斤，就跳過
if (j == free_col) {
continue;
}
if (matrix[i][j] == 0) {
//判斷是否是第一個 0
if (free_row == -1) {
free_row = i;
free_col = j;
//初始化行標(biāo)記位為 0，如果之前是 0 就置為 1
for (int k = 0; k < matrix.length; k++) {
if (matrix[k][free_col] == 0) {
matrix[k][free_col] = 1;
} else {
matrix[k][free_col] = 0;
}
}
//初始化列標(biāo)記位為 0槐沼，如果之前是 0 就置為 1
for (int k = 0; k < matrix[free_row].length; k++) {
if (matrix[free_row][k] == 0) {
matrix[free_row][k] = 1;
} else {
matrix[free_row][k] = 0;
}
}
break;
//找 0 的位置曙蒸，將相應(yīng)的標(biāo)志置 1
} else {
matrix[i][free_col] = 1;
matrix[free_row][j] = 1;
}
}
}
}
if (free_row != -1) {
//將標(biāo)志位為 1 的所有列置為 0
for (int i = 0; i < col; i++) {
if (matrix[free_row][i] == 1) {
setColZeroes(matrix, i);
}
}
//將標(biāo)志位為 1 的所有行置為 0
for (int i = 0; i < row; i++) {
if (matrix[i][free_col] == 1) {
setRowZeroes(matrix, i);
}
}
}
}
private void setColZeroes(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
private void setRowZeroes(int[][] matrix, int row) {
for (int i = 0; i < matrix[row].length; i++) {
matrix[row][i] = 0;
}
}
時間復(fù)雜度：O ( mn )。
空間復(fù)雜度：O（1）岗钩。
leetcode解法三和我的思想是一樣的纽窟，它標(biāo)記位直接用第一行和第一列，由于第一行和第一列不一定會被置為 0兼吓，所以需要用 isCol 變量來標(biāo)記第一列是否需要置為 0臂港，用 matrix[0][0] 標(biāo)記第一行是否需要置為 0。它是將用 0 表示當(dāng)前行（列）需要置 0视搏，這一點也很巧妙审孽，相比我上邊的算法就不需要初始化標(biāo)記位了。
class Solution {
public void setZeroes(int[][] matrix) {
Boolean isCol = false;
int R = matrix.length;
int C = matrix[0].length;
for (int i = 0; i < R; i++) {
//判斷第 1 列是否需要置為 0
if (matrix[i][0] == 0) {
isCol = true;
}
//找 0 的位置浑娜，將相應(yīng)標(biāo)記置 0
for (int j = 1; j < C; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
//根據(jù)標(biāo)志佑力，將元素置 0
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
//判斷第一行是否需要置 0
if (matrix[0][0] == 0) {
for (int j = 0; j < C; j++) {
matrix[0][j] = 0;
}
}
//判斷第一列是否需要置 0
if (isCol) {
for (int i = 0; i < R; i++) {
matrix[i][0] = 0;
}
}
}
}
總
這道題如果對空間復(fù)雜度沒有要求就很簡單了，對于空間復(fù)雜度的優(yōu)化棚愤，充分利用給定的空間的思想很經(jīng)典了搓萧。
更多詳細(xì)通俗題解詳見 leetcode.wang 。
