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

相关文章

来自专栏飞雪无情的博客

Go语言性能优化-两数之和算法性能研究

好多人都在刷leetcode,今天我也注册了一个玩玩,发现里面好多都是算法题,好吧,毕业十来年,学的那点可怜的数学知识,全都还给学校了。好了闲话少说,言归正传,...

2043
来自专栏数据结构与算法

P1044 栈

题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一...

3116
来自专栏程序员的SOD蜜

Why to do,What to do,Where to do 与 Lambda表达式!

最近我做一个“四象限”图表控件,其中有一个比较复杂的“坐标变换”问题,即是如何让一组数据放到有限的一个区间内,例如有一组数据 List[4,5,6,7,8],要...

2349
来自专栏从流域到海域

Python 列表生成式(List Comprehensions)

列表生成式(List Comprehensions),顾名思义,即为生成列表的表达式。列表生成式是Python内置的高级特性,简单却功能强大,充分体现了Pyt...

2078
来自专栏潇涧技术专栏

Python Data Structures - C1 Search

参考内容: 1.Problem Solving with Python Chapter5: Search and Sorting online_link ...

711
来自专栏用户画像

C语言测试题

2. 假设已指定i为整型变量,f为float变量,d为double型变量,e为long型,有下面式子:

1915
来自专栏大数据架构

UML(一) 类图详解

2796
来自专栏数据结构与算法

2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对...

3304
来自专栏Fish

CUDA PTX ISA阅读笔记(二)

8. 第八章 指令集 这一章占了整个手册的一大半(百十来页吧),主要介绍各种指令,虽然页数很多,但是大多数指令都很简单。 8.1. 指令的形式和语义描述 这章就...

5275
来自专栏章鱼的慢慢技术路

Luhn算法检验和验证

2466

扫码关注云+社区

领取腾讯云代金券