leetcode 面试经典 150 题：矩阵置零

题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

• 示例 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
  -2³¹ <= matrix[i][j] <= 2³¹ - 1

• 进阶：
  一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。 你能想出一个仅使用常量空间的解决方案吗？

题解

1. 核心要点：
   • 标记0的位置：
     使用两个向量 row 和 col 来分别标记包含0的行和列。row 的长度为矩阵的行数 m，col 的长度为矩阵的列数 n。初始时，所有元素都设置为 false。
   • 遍历矩阵：
     第一个循环遍历矩阵的每个元素 matrix[i][j]。
     如果发现元素值为0，则将对应的 row[i] 和 col[j] 标记为 true。
   • 置零操作：
     第二个循环再次遍历矩阵，根据 row 和 col 的标记，将对应的行和列置零。
2. 时间复杂度：O(mn)
3. 空间复杂度：O(m+n)
4. c++ 实现算法：

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;
                }
            }
        }
    }
};

5. 演示：以示例1为例

假设我们有以下矩阵：

[
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
我们需要将所有包含0的行和列置零。

第一步：标记0的位置
我们使用两个向量 row 和 col 来标记包含0的行和列。

遍历矩阵的每个元素：
当我们遇到 matrix[1][1] = 0 时，我们将 row[1] 和 col[1] 标记为 true。
标记后的 row 和 col 向量如下：

row: [false, true, false]
col: [false, true, false]

第二步：置零操作
根据 row 和 col 的标记，我们将对应的行和列置零。

遍历矩阵的每个元素：
对于 matrix[1][0]，由于 row[1] 为 true，我们将其置零。
对于 matrix[1][1]，它已经是零，保持不变。
对于 matrix[1][2]，由于 row[1] 为 true，我们将其置零。
对于 matrix[0][1] 和 matrix[2][1]，由于 col[1] 为 true，我们将其置零。

最终得到的矩阵如下：

[
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
]

6. c++ 完整demo：

#include <vector>
#include <iostream>

using namespace std;

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;
                }
            }
        }
    }
};

// 用于打印矩阵的函数
void printMatrix(const vector<vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

int main() {
    // 创建一个示例矩阵
    vector<vector<int>> matrix = {
        {1, 1, 1},
        {1, 0, 1},
        {1, 1, 1}
    };
    
    cout << "Original matrix:" << endl;
    printMatrix(matrix);
    
    Solution solution;
    solution.setZeroes(matrix);
    
    cout << "Matrix after setting zeros:" << endl;
    printMatrix(matrix);
    
    return 0;
}