文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++实现LeetCode(73.矩阵赋零)

2024-04-02 19:55

关注

[LeetCode] 73.Set Matrix Zeroes 矩阵赋零

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

据说这题是CareerCup上的原题,我还没有刷CareerCup,所以不知道啦,不过这题也不算难,虽然我也是看了网上的解法照着写的,但是下次遇到绝对想的起来。这道题中说的空间复杂度为O(mn)的解法自不用多说,直接新建一个和matrix等大小的矩阵,然后一行一行的扫,只要有0,就将新建的矩阵的对应行全赋0,行扫完再扫列,然后把更新完的矩阵赋给matrix即可,这个算法的空间复杂度太高。将其优化到O(m+n)的方法是,用一个长度为m的一维数组记录各行中是否有0,用一个长度为n的一维数组记录各列中是否有0,最后直接更新matrix数组即可。这道题的要求是用O(1)的空间,那么我们就不能新建数组,我们考虑就用原数组的第一行第一列来记录各行各列是否有0.

- 先扫描第一行第一列,如果有0,则将各自的flag设置为true
- 然后扫描除去第一行第一列的整个数组,如果有0,则将对应的第一行和第一列的数字赋0
- 再次遍历除去第一行第一列的整个数组,如果对应的第一行和第一列的数字有一个为0,则将当前值赋0
- 最后根据第一行第一列的flag来更新第一行第一列

代码如下:


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 rowZero = false, colZero = false;
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) colZero = true;
        }
        for (int i = 0; i < n; ++i) {
            if (matrix[0][i] == 0) rowZero = true;
        } 
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowZero) {
            for (int i = 0; i < n; ++i) matrix[0][i] = 0;
        }
        if (colZero) {
            for (int i = 0; i < m; ++i) matrix[i][0] = 0;
        }
    }
};

到此这篇关于C++实现LeetCode(73.矩阵赋零)的文章就介绍到这了,更多相关C++实现矩阵赋零内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯