专栏首页chenjx85的技术专栏leetcode-73-矩阵置零

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 条评论
登录 后参与评论

相关文章

  • 关于c++11中的thread库

    c++11中新支持了thread这个库,常见的创建线程、join、detach都能支持。

    chenjx85
  • leetcode-53-Maximum Subarray(动态规划详解)

    chenjx85
  • vector.clear()不能用来清零

    vector.clear()函数并不会把所有元素清零,笔者就曾经这样幻想过这个函数的作用,然而事实证明并不是。

    chenjx85
  • Leetcode 59. Spiral Matrix II

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • Leetcode 48. Rotate Image

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • N(奇数)阶幻方-java实现代码

    看完最强大脑,有一期是说N阶幻立方的,作为一个程序员,我的第一反应时我可以用程序实现,在此公布N(奇数)阶幻方的java实现代码:

    lzugis
  • 有序矩阵中第K小的元素

    给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。

    你的益达
  • 162. 矩阵归零先找为零的位置,再分别置零

    给定一个m×n矩阵,如果一个元素是0,则将其所在行和列全部元素变成0。 需要在原矩阵上完成操作。

    和蔼的zhxing
  • HDU 1875 畅通工程再续(kruskal)

    畅通工程再续 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

    ShenduCC
  • LeetCode 454. 四数相加 II(哈希)

    给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l]...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券