leetcode-73-矩阵置零

题目描述:

给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 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(mn) 的额外空间,但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
  • 你能想出一个常数空间的解决方案吗?

要完成的函数:

void setZeroes(vector<vector<int>>& matrix) 

说明:

1、这道题给定一个二维vector,要求把矩阵中0元素的行和列上的所有元素都置0,要求原地修改。

2、这道题其实如果先存储0元素的位置,多费点空间,这道题是可以很迅速地解决的。

空间复杂度是O(mn)的代码如下:

    void setZeroes(vector<vector<int>>& matrix) 
    {
        int hang=matrix.size(),lie=matrix[0].size();
        vector<int>record;//存储0元素的行坐标、列坐标
        for(int i=0;i<hang;i++)
        {
            for(int j=0;j<lie;j++)
            {
                if(matrix[i][j]==0)
                {
                    record.push_back(i);//行坐标在前
                    record.push_back(j);//列坐标在后
                }
            }
        }
        for(int i=0;i<record.size();i+=2)
        {
            for(int j=0;j<lie;j++)//先处理同一行的
                matrix[record[i]][j]=0;
            for(int j=0;j<hang;j++)//再处理同一列的
                matrix[j][record[i+1]]=0;
        }
    }

上述代码实测44ms,beats 99.66% of cpp submissions。时间复杂度是可以满足的。

改进:

如果想改成O(m+n)的时间复杂度,那要怎么做?

也很容易,我们不要记0元素的位置了,我们记哪几行哪几列需要置0。

代码也很容易,如下:

    void setZeroes(vector<vector<int>>& matrix) 
    {
        int hang=matrix.size(),lie=matrix[0].size();
        vector<int>hangrecord,lierecord;
        for(int i=0;i<hang;i++)
        {
            for(int j=0;j<lie;j++)
            {
                if(matrix[i][j]==0)
                {
                    hangrecord.push_back(i);//第i行要置为0
                    break;
                }
            }
        }
        for(int j=0;j<lie;j++)
        {
            for(int i=0;i<hang;i++)
            {
                if(matrix[i][j]==0)
                {
                    lierecord.push_back(j);//第j列要置为0
                    break;
                }
            }
        }
        for(int i=0;i<hangrecord.size();i++)//逐个处理行
        {
            matrix[hangrecord[i]]=vector<int>(lie,0);//整一行置为0的vector
        }
        for(int i=0;i<lierecord.size();i++)//逐个处理列
        {
            for(int j=0;j<hang;j++)
            {
                matrix[j][lierecord[i]]=0;
            }
        }
    }

上述代码实测44ms,beats 99.66% of cpp submissions。

其实笔者看到其他博客还有常数空间复杂度的做法,但这两天状态不是很好,也就没仔细钻研,等之后再来补吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

numpy用法小结

前言   个人感觉网上对numpy的总结感觉不够详尽细致,在这里我对numpy做个相对细致的小结吧,在数据分析与人工智能方面会有所涉及到的东西在这里都说说吧,也...

44340
来自专栏蜉蝣禅修之道

Next Permutation之字典序法

17060
来自专栏机器之心

入门 | 数据科学初学者必知的NumPy基础知识

选自TowardsDataScience 作者:Ehi Aigiomawu 机器之心编译 参与:李诗萌、路 本文介绍了一些 NumPy 基础知识,适合数据科学初...

28630
来自专栏程序生活

Tensorflow教程(十三) tf.Variable() 和tf.get_variable()1 简介2 区别3 实例

23530
来自专栏王肖的UT

GLSL-内置函数

66830
来自专栏数据小魔方

左手用R右手Python系列8——数据去重与缺失值处理

因为最近事情略多,最近更新的不勤了,但是学习的脚步不能停,一旦停下来,有些路就白走了,今天就盘点一下R语言和Python中常用于处理重复值、缺失值的函数。 在R...

34940
来自专栏前端黑板报

一个数字截取引发的精度问题(四)

这篇是精度问题的最后一篇,要是想看前面的,请看微信历史记录。 做前端的都感觉JS这语言巨坑无比,兼容性让你摸不到头脑,甚至还会让你脱发。一些初学者遇到: 0.1...

257100
来自专栏CDA数据分析师

入门 | 数据科学初学者必知的NumPy基础知识

NumPy(Numerical Python)是 Python 中的一个线性代数库。对每一个数据科学或机器学习 Python 包而言,这都是一个非常重要的库,S...

14020
来自专栏和蔼的张星的图像处理专栏

138. 子数组之和 map存储加规律

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。 假定一定存在这样的字数组。 样例 给出 [-3, 1, 2,...

12710
来自专栏人工智能

如何为机器学习索引,切片,调整 NumPy 数组

具体在 Python 中,数据几乎被都被表示为 NumPy 数组。

76570

扫码关注云+社区

领取腾讯云代金券