leetcode-73-矩阵置零

chenjx85

发布于 2018-08-30 17:22:14

7010

发布于 2018-08-30 17:22:14

文章被收录于专栏：chenjx85的技术专栏chenjx85的技术专栏

题目描述：

给定一个 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。

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-08-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度