My code:
public class Solution {
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return;
int row = matrix.length;
int col = matrix[0].length;
boolean[] rowIsZero = new boolean[row];
boolean[] colIsZero = new boolean[col];
boolean[][] isVisited = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0 && !isVisited[i][j]) {
if (!rowIsZero[i]) {
for (int temp = 0; temp < col; temp++) {
if (matrix[i][temp] != 0) {
isVisited[i][temp] = true;
matrix[i][temp] = 0;
}
}
rowIsZero[i] = true;
}
if (!colIsZero[j]) {
for (int temp = 0; temp < row; temp++) {
if (matrix[temp][j] != 0) {
isVisited[temp][j] = true;
matrix[temp][j] = 0;
}
}
colIsZero[j] = true;
}
}
}
}
}
}
My test result:
做法比較直接蜈七。用多了空間柴底。所以我的做法不需要考慮婿脸。網(wǎng)上查到的一種做法，只需要柄驻，常數(shù)級別的空間狐树。理解下吧。
http://chenpindian.com/2014/12/18/post-4/
我太累了鸿脓。還在倒時(shí)差抑钟，就逼著自己寫代碼，當(dāng)心剛剛有些起色的身體有跨了野哭。
睡了味赃。
**
總結(jié)：matrix， 從四周下手虐拓。再從內(nèi)部矩形下手心俗。
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return;
boolean firstColZero = false;
boolean firstRowZero = false;
/** detect whether first row has zeros */
for (int i = 0; i < matrix[0].length; i++) {
if (matrix[0][i] == 0) {
firstRowZero = true;
break;
}
}
/** detect whether first col has zeros */
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
/** mark first row and col according to the inside elements */
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
/** mark zeros for all rows and cols except first row and col according to their elements */
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0)
matrix[i][j] = 0;
}
}
/** mark first col and row according to whether first row and col have zeros */
if (firstColZero) {
for (int i = 0; i < matrix.length; i++)
matrix[i][0] = 0;
}
if (firstRowZero) {
for (int i = 0; i < matrix[0].length; i++)
matrix[0][i] = 0;
}
}
}
這道題目是看了提示才做出來的。也不能這么說。
對于space - O(m + n) 我是有辦法的城榛。用一個(gè)ArrayList記錄下所有需要?dú)w0的列號(hào)和行號(hào)揪利。然后再全部統(tǒng)一歸0.
但是，constant space 的做法狠持，我并沒有想出來疟位。
Fuck it.
然后看了這個(gè)提示。上面的網(wǎng)頁鏈接壞了喘垂√鹂蹋看下面這個(gè)。
http://www.programcreek.com/2012/12/leetcode-set-matrix-zeroes-java/
想想也是正勒，第一行得院，第一列，其實(shí)是可以表征整個(gè)matrix狀態(tài)的章贞。所以
遍歷 i = 1 : length -1, j = 1 : length - 1, 即內(nèi)側(cè)的子matrix祥绞，如果是0，則將相應(yīng)的第一行第一列對應(yīng)的元素設(shè)置為0.然后最后再次遍歷這個(gè)sub matrix鸭限。如果他對應(yīng)的第一行第一列只要有一者為0蜕径，他就set zero
同時(shí)，這么做之后败京，就不能確定第一行第一列是否全0了兜喻，因?yàn)榻o內(nèi)部matrix在其上set了zero，就不能確定該zero是他自己本身就有的赡麦，還是后來被set的朴皆。
所以一開始就要先遍歷first row and col to ensure whether they contain zeros.
然后最后，根據(jù)這兩個(gè)標(biāo)志位隧甚。如果含0车荔，就把對應(yīng)的第一行或者第一列全部設(shè)置為0
That' it.
Anyway, Good luck, Richardo!
My code:
public class Solution {
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
boolean col = false;
boolean row = false;
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
col = true;
break;
}
}
for (int i = 0; i < matrix[0].length; i++) {
if (matrix[0][i] == 0) {
row = true;
break;
}
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[i][j] = 0;
}
}
}
for (int i = 1; i < matrix[0].length; i++) {
if (matrix[0][i] == 0) {
for (int j = 0; j < matrix.length; j++) {
matrix[j][i] = 0;
}
}
}
if (col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][0] = 0;
}
}
if (row) {
for (int i = 0; i < matrix[0].length; i++) {
matrix[0][i] = 0;
}
}
return;
}
}
對這道題還算是有點(diǎn)印象渡冻。所以做了出來戚扳，而且是 O(1)
Anyway, Good luck, Richardo! --08/09/2016
