复杂度分析

时间复杂度: O ( m n ) O(mn) O(mn) m m m 为矩阵 matrix 的行数, n n n 为矩阵的列数。

空间复杂度: O ( m + n ) O(m+n) O(m+n)

方法三:仅使用2个额外变量的常量空间复杂度

我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组,以达到 O ( 1 ) O(1) O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改,无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0

在实际代码中,我们首先预处理出两个标记变量,接着使用其他行与列去处理第一行与第一列,然后反过来使用第一行与第一列去更新其他行与列,最后使用两个标记变量更新第一行与第一列即可。

实现代码

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

        int i, j;
        int row0 = 0, col0 = 0;
        // 第一列
        for(i = 0; i < m; ++i){
            if(matrix[i][0] == 0){
                col0 = 1;
            }
        }
        // 第一行
        for(j = 0; j < n; ++j){
            if(matrix[0][j] == 0){
                row0 = 1;
            }
        }

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

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

        if(col0){
            for(i = 0; i < m; ++i){
                matrix[i][0] = 0;
            }
        }
        if(row0){
            for(j = 0; j < n; ++j){
                matrix[0][j] = 0;
            }
        }
    }
};
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
class="hide-preCode-box">

复杂度分析

时间复杂度: O ( m n ) O(mn) O(mn) m m m 为矩阵 matrix 的行数, n n n 为矩阵的列数。

空间复杂度: O ( 1 ) O(1) O(1)


写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 ???。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 ? 哦。

>>
注:本文转载自blog.csdn.net的wang_nn的文章"https://blog.csdn.net/weixin_54383080/article/details/133463306"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接

评论记录:

未查询到任何数据!