LeetCode73.矩阵置零

admin2024-05-15  0

题目链接:

73. 矩阵置零 - 力扣(LeetCode)

分析:普通的模拟问题,我们按照题目的要求进行模拟,把需要的位置置0即可。

算法思路:题目要求原地计算,所以迁移这个矩阵是不现实的。这里引出一种比较常用的思路,我们首先定义两个一位数组,分别表示对应的行、列出现的0的个数。例如下面代码中的v1,其中v1[i]表示第i行出现的0的个数;同理v2[j]表示第j列出现的0的个数,这样一来问题被极大的简化了。

我们遍历整个矩阵,统计每一行、列是否出现了0,出现一次则对标记做一个对应的修改。遍历结束以后。我们再次遍历,对每个元素,我们可以在O(1)的时间内得知其所在的行/列是否有0,如果有则直接将该元素也修改为0;否则该元素不变。处理完成后,就得到了最终的结果。

参考代码:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();//统计矩阵的边长
        vector<int>v1(m,0);//表示各行出现0的情况
        vector<int>v2(n,0);//表示各列出现0的情况
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if(matrix[i][j]==0){//遍历矩阵 统计各行/列出现0的次数
                    v1[i]++;
                    v2[j]++;
                }
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j){
                if(v1[i]>0||v2[j]>0)//对于每个元素 如果所在的行/列有0 那么把该元素置0
                    matrix[i][j]=0;
            }
    }
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!