(Leetcode 2021 刷题计划) 73. 矩阵置零
原创
题目
给定一个 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.lengthn == matrix[0].length1 <= 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 删除。
评论
登录后参与评论
推荐阅读
目录