题目描述

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

样例

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

示例 2:
输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

算法1

(模拟) $O(n^2 * (n + n))$

遍历矩阵，把要置0的非零元素置为一个不会取到的值；
再遍历一次矩阵，把不会取到的值变成0。

时间复杂度

遍历矩阵两次，故$O(n^2)$；
第一次遍历时，对每个位置做了$O(n + n)$的操作；
所以总的时间复杂度是$O(n^2 * (n + n))$

参考文献

C++ 代码

class Solution {
private:
    int tmp = -10000;
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();

        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (matrix[i][j] == 0){
                    for (int r = 0; r < m; ++r)
                        if (matrix[r][j] != 0) 
                            matrix[r][j] = tmp;
                    for (int c = 0; c < n; ++c)
                        if (matrix[i][c] != 0)
                            matrix[i][c] = tmp;
                }
            }
        }

        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (matrix[i][j] == tmp) matrix[i][j] = 0;
            }
        }

    }
};

算法2

(模拟) $O(n^2)$

先使用变量记录第一行、第一列需不需要置0；
再遍历矩阵剩余部分，并使用矩阵的第一行第一列记录该列或者该行是否需要置0；
遍历矩阵，根据第一行第一列，将该置0的置0；
根据变量，对第一行和第一列该置0的置0。

时间复杂度

常数次遍历矩阵，故$O(n^2)$。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();

        bool row_zero = false, col_zero = false;
        for (int i = 0; i < m; ++i)
            if (!matrix[i][0]) col_zero = true;

        for (int j = 0; j < n; ++j)
            if (!matrix[0][j]) row_zero = true;

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (matrix[i][j] == 0)
                    matrix[i][0] = matrix[0][j] = 0;

        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;

        if (row_zero)
            for (int j = 0; j < n; ++j) matrix[0][j] = 0;

        if (col_zero)
            for (int i = 0; i < m; ++i) matrix[i][0] = 0;
    }
};