73. 矩阵置零

• 题目链接

set(C++)

• 使用set存储带有0的行和列

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        set<int> row;
        set<int> line;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    row.insert(i);
                    line.insert(j);
                }
            }
        }
        
        set<int>::iterator it1;
        for(it1=row.begin();it1!=row.end();it1++)  //使用迭代器进行遍历   
        {  
            int x = *it1;  
            for(int j = 0; j < n; j++){
                matrix[x][j] = 0;
            }
        } 
        set<int>::iterator it2;
        for(it2=line.begin();it2!=line.end();it2++){
            int y = *it2;
            for(int i = 0; i < m; i++){
                matrix[i][y] = 0;
            }
        }
    }
};

• 空间复杂度：O(m+n)
• 时间复杂度：O(mn)