给定一个?m x n
的矩阵,如果一个元素为 0
,则将其所在行和列的所有元素都设为 0
。请使用 原地 算法。
进阶:
O(mn)
?的额外空间,但这并不是一个好的解决方案。O(m?+?n)
的额外空间,但这仍然不是最好的解决方案。示例 1:
输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]
示例 2:
输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
解题思路: 该方法是直接利用额外数组构建对应的行列状态, 从而重新扫描置零, 编码相对简单
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<int> row(m), col(n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!matrix[i][j]) {
row[i] = col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
};
O(mn)
O(m + n)
解题思路: 为了节省空间,利用第一行和第一列作为行列的状态数组, 但是需要保留其中第一行和第一列是否需要全部置零的状态
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool colZero = false, rowZero = false;
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == 0) {
colZero = true;
break;
}
}
for (int i = 0; i < n; ++i) {
if (matrix[0][i] == 0) {
rowZero = true;
break;
}
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
}
if (colZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (rowZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}
};
O(mn)
O(1)
解题思路: 更进一步, 采用单标记变量, 但是需要行扫描从尾行开始(如果采用尾行标记,则从首行开始扫描)
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool colZero = false;
for (int i = 0; i < m; i++) {
if (!matrix[i][0]) {
colZero = true;
}
for (int j = 1; j < n; j++) {
if (!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 1; j < n; j++) {
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
if (colZero) {
matrix[i][0] = 0;
}
}
}
};
O(mn)
O(1)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。