LeetCode 73. Set Matrix Zeroes

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 73. Set Matrix Zeroes 原题链接中等

作者：

yxc , 2018-05-01 00:30:37 , 所有人可见 , 阅读 3758

13

1

题目描述

给定一个 $n * m$ 的矩阵，对于其中是0的元素，把它所在的整行整列都置成0。
请使用 原地算法，即只能使用额外 $O(1)$ 的空间。

样例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]
]

算法

(原地算法) $O(nm)$

我们只需统计出矩阵中每一行或者每一列是否有0，然后把含有0的行或者列都置成0即可。

用两个变量记录第一行和第一列是否有0。
遍历整个矩阵，用矩阵的第一行和第一列记录对应的行和列是否有0。
把含有0的行和列都置成0。

时间复杂度分析：矩阵中每个元素只遍历常数次数，所以时间复杂度是 $(nm)$。
空间复杂度分析：只用了两个额外的变量记录第一行和第一列是否含有0，所以额外的空间复杂度是 $(1)$，满足原地算法的要求。

C++ 代码

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty()) return;
        int n = matrix.size(), m = matrix[0].size();
        int col0 = 1, row0 = 1;
        for (int i = 0; i < n; i ++ )
            if (!matrix[i][0]) col0 = 0;
        for (int i = 0; i < m; i ++ )
            if (!matrix[0][i]) row0 = 0;
        for (int i = 1; i < n; i ++ )
            for (int j = 1; j < m; j ++ )
                if (!matrix[i][j])
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
        for (int i = 1; i < n; i ++ )
            if (!matrix[i][0])
                for (int j = 1; j < m; j ++ )
                    matrix[i][j] = 0;

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

        if (!col0)
            for (int i = 0; i < n; i ++ )
                matrix[i][0] = 0;

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

8 评论

Draper 2020-08-02 19:15

这个代码的实现比直播的时候好懂了很多2333

yxc 2020-08-19 09:38

思路是一样的嘛hh

AcKing. 2021-09-05 22:52

666，看代码确实直观了很多~

天空会变灰色 2022-12-12 15:22

f[0][j]和f[i][0]可以记录第j列，i行的值（i，j大于0）
第0行第0列需要额外用两个bool变量分别存储，因为f[0][0]不能同时记录0行0列情况
要先对1~n行，1~j列进行处理，0行0列最后处理，因为0行0列作为其他行列标志位，如果提前修改就没有意义了

幻か听 2021-03-21 20:11

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        set<pair<int, int>> hashset;

        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]) hashset.insert({i, j});
            }
        }

        for(auto x : hashset){
            int row = x.first, col = x.second;

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

如果把set改成unordered_set，那么会报一个“尝试引用已删除的函数”的错误，有大佬知道这是为什么吗？