矩阵#中等#矩阵置零

前文

给定一个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]]

正文

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

    }
};

解法1

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        // matrix[1][2] = 100;

        set<int> row, col;

        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = 0; j < matrix[i].size(); ++j) {
                if (matrix[i][j] == 0) {
                    row.insert(i);
                    col.insert(j);
                }
            }
        }

        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = 0; j < matrix[i].size(); ++j) {
                if (row.count(i) || col.count(j))
                    matrix[i][j] = 0;
            }
        }

    }
};

只要元素为0则所在行列元素都为0，一个简单的思路是先记录需要被置零的行和列，当然不要重复， 选择set容器记录行和列，最后一起处理，记录后再遍历一遍，如果元素的行列符合则置零即可。 时间复杂度两次循环两个O(n^2)，为O(n^2)