前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >737. Find Elements in Matrix哈希表查找

737. Find Elements in Matrix哈希表查找

作者头像
和蔼的zhxing
发布2018-09-04 11:41:58
2260
发布2018-09-04 11:41:58
举报

Given a matrix, find a element that appear in all the rows in the matrix.You can assume that there is only one such element. 样例

代码语言:javascript
复制
For example:
Given a matrix:
[
  [2,5,3],
  [3,2,1],
  [1,3,5]
]
return 3

哈希表查找

这个倒不是一定得用哈希表,只是用哈希好写一些,而且同一行相同的元素放在哈希表中就只有一个了。 准备两个set<int>分别是res1,res2,首先把第一行放入res1,第二行来的时候在第一行查找(利用find成员函数),能找到的再放入res2,找不到就不要了,然后把res1清空,第三行来的时候反过来在res2中查找,能找到的放入res1,然后把res2清空,以此类推,重复说上述步骤,最后留下的set里的数就会越来越少,直到最后只剩一个数(这个题假定只有一个这样的数),实际上如果多几个数的话这样的代码也是可以的。

代码语言:javascript
复制
    int FindElements(vector<vector<int>> &Matrix) {
        set<int> res1;
        set<int> res2;
        auto s1=Matrix.size();
        auto s2=Matrix[0].size();
        for(int i=0;i<s1;i++)
        {
            for(int j=0;j<s2;j++)
            { 
                if(i==0)       //第一行先插入进去
                res1.insert(Matrix[i][j]);
                else if(i%2!=0)
                {
                    if(res1.find(Matrix[i][j])!=res1.end())   //如果能在s1中找到,就存在s2里。
                    res2.insert(Matrix[i][j]);
                    
                   
                }
                else if(i%2==0)
                {
                    if(res2.find(Matrix[i][j])!=res2.end())   //如果能在s2中找到,就存在s1里。
                    res1.insert(Matrix[i][j]);
                    
                   
                }
            }
            if(i%2!=0)
            res1.clear();
            if(i%2==0)
            res2.clear();         //这两个清空一定不要写在循环里了。
    
        }
        if(res1.size()==1)
        return *res1.begin();
        if(res2.size()==1)
        return *res2.begin();
        // write your code here
    }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.01.08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 哈希表查找
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档