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:
做法比较直接。用多了空间。所以我的做法不需要考虑。网上查到的一种做法，只需要，常数级别的空间。理解下吧。
http://chenpindian.com/2014/12/18/post-4/
我太累了。还在倒时差，就逼着自己写代码，当心刚刚有些起色的身体有跨了。
睡了。
**
总结：matrix， 从四周下手。再从内部矩形下手。
**
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) 我是有办法的。用一个ArrayList记录下所有需要归0的列号和行号。然后再全部统一归0.
但是，constant space 的做法，我并没有想出来。
Fuck it.
然后看了这个提示。上面的网页链接坏了。看下面这个。
http://www.programcreek.com/2012/12/leetcode-set-matrix-zeroes-java/
想想也是，第一行，第一列，其实是可以表征整个matrix状态的。所以
遍历 i = 1 : length -1, j = 1 : length - 1, 即内侧的子matrix，如果是0，则将相应的第一行第一列对应的元素设置为0.然后最后再次遍历这个sub matrix。如果他对应的第一行第一列只要有一者为0，他就set zero
同时，这么做之后，就不能确定第一行第一列是否全0了，因为给内部matrix在其上set了zero，就不能确定该zero是他自己本身就有的，还是后来被set的。
所以一开始就要先遍历first row and col to ensure whether they contain zeros.
然后最后，根据这两个标志位。如果含0，就把对应的第一行或者第一列全部设置为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;
}
}
对这道题还算是有点印象。所以做了出来，而且是 O(1)
Anyway, Good luck, Richardo! --08/09/2016
