XingHuiSamaの宝藏之地

给定一个 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
-231 <= matrix[i][j] <= 231 - 1

可以开两个数组标记行和列

然后再置零

1. 算法核心思想：分离记录与执行

核心在于“先记账，后办事”。为了避免在修改矩阵时污染后续尚未遍历到的数据，算法申请了两个独立的一维数组，分别充当行和列的“记账本”。第一遍扫描矩阵时，只在账本上记录哪些行和哪些列出现了 0；第二遍扫描时，完全脱离原矩阵的状态，仅根据账本上的记录，直接对相应的行和列执行清零操作。

2. 逻辑拆解

构建记账本（初始化）：开辟了两个一维数组 m 和 n，初始值全部设为 1。根据代码逻辑，m 的长度等于列数，用于监控每一列的状态；n 的长度等于行数，用于监控每一行的状态。
第一遍摸底排查（记录 0 的位置）：利用两层嵌套的 for 循环遍历整个二维矩阵。一旦发现 matrix[i][j] == 0，立刻在账本上做好标记：把对应的列账本 m[j] 设为 0，对应的行账本 n[i] 设为 0。这一步绝对不去碰原矩阵的其他元素。
第二遍秋后算账（执行清零）：
- 处理列：遍历列账本 m，如果发现 m[i] == 0，说明第 i 列必须全部清零。于是通过一个内部循环，把该列从上到下扫一遍，全部赋值为 0。
- 处理行：同理，遍历行账本 n，如果发现 n[i] == 0，说明第 i 行必须全部清零。通过内部循环，把该行从左到右扫一遍，全部赋值为 0。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<int> m = vector<int>(matrix[0].size(), 1);
        vector<int> n = vector<int>(matrix.size(), 1);
        for (int i = 0;i < matrix.size();i++) {
            for (int j = 0;j < matrix[0].size();j++) {
                if (matrix[i][j] == 0) {
                    m[j] = 0;
                    n[i] = 0;
                }
            }
        }

        //m表示列
        //n表示行

        for (int i = 0;i < m.size();i++) {
            if (m[i] == 0) {
                for (int j = 0;j < n.size();j++) {
                    matrix[j][i] = 0;
                }
            }
        }

        for (int i = 0; i < n.size();i++) {
            if (n[i] == 0) {
                for (int j = 0;j < m.size();j++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

3. 复杂度剖析

时间复杂度：O(M N)。（其中 M 为行数，N 为列数）。第一遍排查遍历了整个矩阵，耗时 O(M N)。第二遍清零操作，最坏情况下（全是 0）也只是将整个矩阵再遍历一次，整体依然保持在线性级别。
空间复杂度：O(M + N)。为了记录行和列的状态，额外开辟了长度分别为 M 和 N 的两个 vector 数组。