专栏首页和蔼的张星的图像处理专栏162. 矩阵归零先找为零的位置,再分别置零

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

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

样例 给出一个矩阵

[
  [1, 2],
  [0, 3]
]

返回

[
  [0, 2],
  [0, 0]
]

先找为零的位置,再分别置零

一种显而易见的方法是先找到为零的位置,把这些位置记下来,然后根据这些位置来进行进行一整行或者一整列清除。 记录位置的时候可以用vector<pair<int,int>>来一组一组来记录,这样是最直观的。我一开始的程序也是这么写的,没有什么问题。 后来发现,如果某一行或者某一列出现多个0的话,上面的方法没有避免重复,可能在前面的操作中都已经清零过了,所以想到可以吧row和col分别用一个set来记录,顺便去重,然后分别遍历两个set,这样就可以保证不做重复的事情,不出意外程序快乐1/3左右。两个版本的程序我都保留贴在下面:

    /*
    //使用pair的主程序
    void setZeroes(vector<vector<int>> &matrix) {
        vector<pair<int,int>> ZerosPos;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==0)
                ZerosPos.push_back(make_pair(i,j));
            }
        }
        for(auto zp:ZerosPos)
        {
            setZeroR(matrix,zp.first);
            setZeroC(matrix,zp.second);
        }
        
        // write your code here
    }
    */
  //使用set的主程序
    void setZeroes(vector<vector<int>> &matrix) {
        set<int> row;
        set<int> col;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==0)
                {row.insert(i);
                col.insert(j);
                }
            }
        }
        for(auto r:row) setZeroR(matrix,r);
        for(auto c:col)  setZeroC(matrix,c);
        
        
        // write your code here
    }
    static void setZeroR(vector<vector<int>> &mat,int row)
    {
        mat[row]=vector<int>(mat[row].size(),0);      //整行直接置零
    } 
    static void setZeroC(vector<vector<int>> &mat,int col)
    {
        for(int i=0;i<mat.size();i++)
        mat[i][col]=0;             //这一列置零,因为在不同的vector<int>中,所以只能这么一个一个做。
    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 161. 旋转图像交换加转置

    样例 给出一个矩形[[1,2],[3,4]],90度顺时针旋转后,返回[[3,1],[4,2]]

    和蔼的zhxing
  • 544. 前K大数优先队列

    在一个数组中找到前K大的数 样例 给出 [3,10,1000,-99,4,100], k = 3. 返回 [1000, 100, 10]

    和蔼的zhxing
  • 剑指offer刷题记(C++版本)

    也算是临时抱佛脚了吧,3月之前刷了lintcode100多道题吧,后来发文章什么的就放下了,最近秋招在即在牛客网上想着把剑指offer这本书刷完,尽量早刷完吧,...

    和蔼的zhxing
  • leetcode-73-矩阵置零

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

    chenjx85
  • 跳槽必刷算法题系列(一)

    第74题:编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

    程序员小浩
  • OJ刷题记录:L1-108-神奇的水管(20分)

    X星球上的水路布局所使用的水管是很特殊的, 一共有6个开口, 上,下,左,右,左上,右下. 假定我们将两个开口相连的水管认为是同一个水管, 请你编程求出X星球上...

    英雄爱吃土豆片
  • Leetcode 59. Spiral Matrix II

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

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

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

    你的益达
  • 46. 全排列【回溯算法】

    输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], ...

    韩旭051
  • 树的重心(个人模版)

    树的重心(树的重心定义为:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心) 1 #include<stdio.h> 2 #inc...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券