美文网首页
73. Set Matrix Zeroes

73. Set Matrix Zeroes

作者: larrymusk | 来源:发表于2017-11-20 23:18 被阅读0次

此方案是O(m+n)还不是最佳方案,
思路很简单,用一个SET记录下来哪些行是零
再用一个SET记录下来哪些列为零。
然后依次对记录下来的行和列填充为零

//满足补充内容的第二点,使用 O(m + n) 额外空间。
//将矩阵中所有 0 元素的所在行,列记录下来。
//将记录下来的行号,整行设为0,将记录下来的列号,整列设为0.

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

    unordered_set<int> seti;
    unordered_set<int> setk;
    
    for (int i = 0 ; i < matrix.size(); i++) {
        for (int k = 0 ; k < matrix[0].size(); k++) {
            if (matrix[i][k] == 0) {
                seti.insert(i);
                setk.insert(k);
            }
        }
    }
    
    unordered_set<int>::iterator s_iter;
    for (s_iter = seti.begin(); s_iter != seti.end(); s_iter++) {
        for (int k = 0 ; k < matrix[0].size(); k++) {
            matrix[*s_iter][k] = 0;
        }
    }
    
    for (s_iter = setk.begin(); s_iter != setk.end(); s_iter++) {
        for (int i = 0; i < matrix.size(); i++) {
            matrix[i][*s_iter] = 0;
        }
    }
}
};

相关文章

网友评论

      本文标题:73. Set Matrix Zeroes

      本文链接:https://www.haomeiwen.com/subject/hyabvxtx.html