题目描述

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零

样例

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

(扫描) $O(n^2)$

找到是0的坐标并保存
找到该坐标把矩阵所在行，列置为0
暂时没想到空间复杂度是O（1）的做法

C++ 代码

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size(),m = matrix[0].size();
        typedef pair<int,int> PII;
        vector<PII> res;
        if(!n || !m)return;
        for(int i = 0 ; i < n; i++)
            for(int j = 0 ; j < m; j++)
            {
                if(matrix[i][j] == 0)
                {
                    res.push_back({i,j});
                }
            }
        for(int i = 0 ; i < res.size();i++)
        {
            int a = res[i].first,b = res[i].second;
            for(int col = 0 ; col < m; col++)matrix[a][col] = 0;
            for(int row = 0 ; row < n; row++)matrix[row][b] = 0;
        }
        return;
    }
};