题目

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

---

示例 1

输入：
matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

输出：
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]

解释：

• matrix[1][1] 为 0，将第 1 行和第 1 列全部置为 0。

---

示例 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]]

解释：

• matrix[0][0] 和 matrix[0][3] 为 0，将第 0 行、第 0 列和第 3 列全部置为 0。

---

提示

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^{31} <= matrix[i][j] <= 2^{31} - 1

实现

class Solution {
private:
    static const int N = 210;
    bool cols[N]; // 列标记
public:
    void setZeroes(vector<vector<int>>& matrix) {
        memset(cols , 0 , sizeof cols); // 清空列标记
        
        for(int i = 0 ; i < matrix.size() ; i ++) {
            bool lineFlag = 0;
            for (int j = 0 ; j < matrix[i].size() ; j ++) {
                if(matrix[i][j] == 0) {
                    lineFlag = 1; cols[j] = true;
                }
            }
            // 在行遍历结束后,置零这一行
            if(lineFlag) memset(matrix[i].data() , 0 , matrix[0].size() * sizeof(int));
        }
	    // 最后处理列
        for(int j = 0 ; j < matrix[0].size() ; j++) {
            if (cols[j]) {
                for(int i = 0 ; i < matrix.size() ; i ++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};