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?
AC代码
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
short orphon = -283492;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
if (matrix[i][j] != 0) continue;
for (int k = 0; k < matrix[0].size(); ++k)
if (matrix[i][k] != 0) matrix[i][k] = orphon;
for (int k = 0; k < matrix.size(); ++k)
if (matrix[k][j] != 0) matrix[k][j] = orphon;
}
}
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[0].size(); ++j)
if (matrix[i][j] == orphon) matrix[i][j] = 0;
}
};
正常解法
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;
short row = -1, col = -1;
bool f = false;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
if (matrix[i][j] == 0) {
row = i;
col = j;
f = true;
break;
}
}
if (f) break;
}
if (row == -1) return; //矩阵中没有0，直接返回
for (int i = 0; i < matrix.size(); ++i) {
if (i == row) continue;
for (int j = 0; j < matrix[0].size(); ++j) {
if (j == col) continue;
if (matrix[i][j] == 0) {
matrix[row][j] = 0;
matrix[i][col] = 0;
}
}
}
for (int i = 0; i < matrix.size(); ++i) {
if (i == row) continue;
for (int j = 0; j < matrix[0].size(); ++j) {
if (j == col) continue;
if (matrix[i][col] == 0 || matrix[row][j] == 0)
matrix[i][j] = 0;
}
}
for (int i = 0; i < matrix.size(); ++i) matrix[i][col] = 0;
for (int j = 0; j < matrix[0].size(); ++j) matrix[row][j] = 0;
}
};
总结
1、自己的解法稍有讨巧，脸滚键盘出了一个不会出现在测试样例中的short类型变量orphon，遍历矩阵，若出现0，则将出现0的那一行和那一列的非零元素改为orphon；第二次遍历矩阵，将所有orphon的值改为0。
2、网上普遍流行的解法是找一个0位置，标记其行row和列col，遍历除去col行和col列的元素，如有0，则将row行和col列对应的元素置0，再次遍历除去col行和col列的元素，如对应row行和col列对应的元素为0，则该位置置0，最后将（row，col）所在行和列元素全部置0
