【LeetCode-数组】矩阵置零

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例：

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

题目链接： https://leetcode-cn.com/problems/set-matrix-zeroes/

思路

首先记录下所有 0 的位置放在队列里，然后根据这些位置来将位置所在的行列置零。代码如下：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        queue<pair<int, int>> q;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]==0) q.push(make_pair(i, j));
            }
        }
        while(!q.empty()){
            int row = q.front().first;
            int col = q.front().second;
            q.pop();
            /*int t = i;
            while(t>=0) matrix[t--][j] = 0;
            t = i;
            while(t<m) matrix[t++][j] = 0;
            t = j;
            while(t>=0) matrix[i][t--] = 0;
            t = j;
            while(t<n) matrix[i][t++] = 0;*/
            for(int i=0; i<n; i++) matrix[row][i] = 0;
            for(int i=0; i<m; i++) matrix[i][col] = 0;
        }
    }
};

• 时间复杂度：O(m x n)
  最坏情况下。
• 空间复杂度：O(m x n)
  最坏情况下。