Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:
Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
难度：medium
题目：给定 m * n 的矩阵，如果某一元素为 0，则将其所在行及列都设为 0。在原矩阵上执行。
一种直接的解法是空间复杂度为 O(mn)
一种简单的改进是空间复杂度为 O(m + n), 但是仍不是最好的。
是否可以用常量空间给出解法。
思路：先统计首行，首列是否含有 0。然后用首行首列来记录其它行列。
Runtime: 1 ms, faster than 99.98% of Java online submissions for Set Matrix Zeroes.Memory Usage: 45.6 MB, less than 0.96% of Java online submissions for Set Matrix Zeroes.
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int row0 = 1, column0 = 1;
// first row
for (int i = 0; i < n; i++) {
if (0 == matrix[0][i]) {
row0 = 0;
}
}
// first column
for (int i = 0; i < m; i++) {
if (0 == matrix[i][0]) {
column0 = 0;
}
}
// other rows and columns
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (0 == matrix[i][j]) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// set 0 for other rows and columns
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (0 == matrix[0][j] || 0 == matrix[i][0]) {
matrix[i][j] = 0;
}
}
}
// set 0 for first row
for (int i = 0; 0 == row0 && i < n; i++) {
matrix[0][i] = 0;
}
// set 0 for first column
for (int i = 0; 0 == column0 && i < m; i++) {
matrix[i][0] = 0;
}
}
}