LeetCode 73 Set Matrix Zeroes

Tag: LeetCode Posted on 2021-06-03 09:51:14 Edited on 2021-06-03 10:17:14 Views: 48

题目分析

https://leetcode.com/problems/set-matrix-zeroes/

要解这道题很简单,主要是其限制了要常数的空间复杂度。

空间复杂度 O(mn) 的解法

新建一个同等大小的布尔矩阵,遍历一遍所给的矩阵,如果遇到 0 的话就把其所属行列标记一下。

时间复杂度 O(mn*(m+n))。

空间复杂度 O(m+n) 的解法

新建一个 m+n 的布尔数组,遍历一遍所给的矩阵,如果遇到 0 的话把数组中第 col 个和 n+row 个标记一下。

时间复杂度 O(mn)。

空间复杂度 O(1) 的解法

思路和上面那个解法相似,不过我们直接用所给矩阵的首行和首列来存。

那首行和首列要怎么标记呢?用第一个元素即可

实际上只用第一个元素是不足以进行标记的,还需要额外一个布尔值,因为首行和首列不是命运共同体, 该点的忽视也导致了我第一次提交 WA。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool flag1 = false;
        bool flag2 = false;
        for(int i=0;i<matrix[0].size();i++) {
            if (matrix[0][i] == 0) {
                flag1 = true;
                break;
            }
        }
        for(int i=0;i<matrix.size();i++) {
            if (matrix[i][0] == 0) {
                flag2 = true;
                break;
            }
        }
        
        for(int i=1;i<matrix.size();i++) {
            for(int j=1;j<matrix[0].size();j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i=1;i<matrix.size();i++) {
            for(int j=1;j<matrix[0].size();j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flag1) {
            for(int i=0;i<matrix[0].size();i++) {
                matrix[0][i] = 0;
            }
        }
        if (flag2) {
            for(int i=0;i<matrix.size();i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

时间复杂度 O(mn)。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/