lintcode162. 矩阵归零

阳光穿透心脏的1/2处 2023-07-06 13:05 40阅读 0赞

给定一个m×n矩阵，如果一个元素是0，则将其所在行和列全部元素变成0。  
需要在原矩阵上完成操作。

样例
    样例 1:
    
    输入:[[1,2],[0,3]]
    输出:[[0,2],[0,0]]
    样例 2:
    
    输入:[[1,2,3],[4,0,6],[7,8,9]]
    输出:[[1,0,3],[0,0,0],[7,0,9]]
    挑战
    你是否使用了额外的空间？
    一个直接的解决方案是使用 O(MN) 的额外空间，但这并不是一个好的方案。
    一个简单的改进方案是使用 O(M + N) 的额外空间，但这仍然不是最好的解决方案。
    你能想出一个常数空间的解决方案吗？

思路：遍历矩阵，找到每一个为0数的行列并记录，对每一行和每一列进行置0即可

class Solution {
        
    public:
        /**
         * @param matrix: A lsit of lists of integers
         * @return: nothing
         */
        void setZeroes(vector<vector<int>> &matrix) {
        
            // write your code here
            if(matrix.size()<=0) return;
            set<int> row;
            set<int> col;
            for (int i = 0; i < matrix.size(); i++) {
        
                /* code */
                for(int j=0; j<matrix[i].size();j++)
                {
        
                    if(matrix[i][j]==0)
                    {
        
                        row.insert(i);
                        col.insert(j);
                    }
                }
            }
            for (auto r : row) {
        
                /* code */
                RowSetZero(matrix,r);
            }
            for (auto c : col) {
        
                /* code */
                ColSetZero(matrix,c);
            }
        }
        void RowSetZero(vector<vector<int>> &matrix,int row)
        {
        
            for (int i = 0; i < matrix[row].size(); i++) {
        
                matrix[row][i]=0;
            }
        }
        void ColSetZero(vector<vector<int>> &matrix,int col)
        {
        
            for (int i = 0; i < matrix.size(); i++) {
        
                matrix[i][col]=0;
            }
        }
    };