547. 两数组的交

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].要求去重,这样还是稍微有点难度。

暴力搜索

最暴力的方法,对于nums1种的每个元素都去nums2种搜索,看是否存在,如果存在,就把这个数放入结果中,因为要求去重,所以放入的时候还要检查一下是否已经存在,我们可以先对两个数组都进行排序来规避这个问题,显然太暴力了,都懒得写,时间估计肯定超时了。

排序+双指针+手动去重

先排序,然后利用双指针把两个数组种都有的数放入res,除了第一次,每次放入的时候检查一下和上一次放入的是否是相同的,如果是相同的就不再放入了。 我也不知道这个怎么会超时:

vector<int> intersection(vector<int> nums1, vector<int> nums2) {
        if(nums1.empty()||nums2.empty())
        return vector<int>();
        vector<int> res1;
        //vector<int> res;
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        int n1,n2;
        for(n1=0,n2=0;n1<nums1.size()&&n2<nums2.size();)
        {
            if(nums1[n1]==nums2[n2])  
            {  
                if(res1.size()==0||*(res1.end()-1)!=nums1[n1])
                res1.push_back(nums1[n1]);
                n1++;
                n2++;
            }
            else if(nums1[n1]<nums2[n1])    n1++;
            else if(nums2[n2]<nums1[n1])    n2++;
            
        }
      
        return res1;
        // write your code here
    }

set暴力去重+双指针。

依次把所有的数都放入set中(就是去重,排序过的),然后利用双指针遍历即可,这个就相当esay了。

 vector<int> intersection(vector<int> nums1, vector<int> nums2)
    {
        set<int> res1;
        set<int> res2;
        vector<int> res;
        for(auto n:nums1)
        {
            res1.insert(n);
        }
        for(auto n:nums2)
        {
            res2.insert(n);
        }
        auto beg1=res1.begin();
        auto beg2=res2.begin();
        auto end1=res1.end();
        auto end2=res2.end();
        for(;beg1!=end1&&beg2!=end2;)
        {
            if(*beg1==*beg2)
            {
                res.push_back(*beg1);
                beg1++;
                beg2++;
            }
            else if(*beg1<*beg2)
            {
                beg1++;
            }
            else if(*beg1>*beg2)
            {
                beg2++;
            }
        }
        return res;
    }

over!

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

java中“==”和equal区别

8个月以后就要正式找工作啦,我觉得现在是时候花时间好好深入研究一下以前比较混肴的知识。这就当作是自我成长的第一步!

691
来自专栏C/C++基础

Linux命令(4)——declare/typeset命令(builtin)

declare命令(别名typeset)属shell内建命令,用于申明shell变量并设置变量属性,或查看已定义的shell变量和函数。若不加上任何参数,则会显...

772
来自专栏开发与安全

从零开始学C++之模板(一):函数模板、函数模板特化、重载函数模板、非模板函数重载

一、引子 考虑求两数较大值函数max(a,b) 对于a,b的不同类型,都有相同的处理形式: return a < b ? b : a; 用已有方法解决:...

2000
来自专栏Python疯子

TebsorFlow基本语法

我的博客即将搬运同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invi...

1372
来自专栏Hongten

python开发_re和counter

=============================================

732
来自专栏枕边书

搭建自己的PHP框架心得(三)

续言 接着完善自己的PHP框架,本次更新的主要内容有: 介绍了异常处理机制 完善了异常和错误处理 数据表跟Model类的映射 异常处理 异常处理:异常处理是编程...

2546
来自专栏申龙斌的程序人生

零基础学编程007:FOR循环

在上篇文章《赋值语句》之后,已经可以输出这个枯燥的《复利数据表》的任意一行数据了,例如用这两条语句: i = 100 print( "(1+0.01) ^", ...

3037
来自专栏用户3030674的专栏

java线程控制安全

在线程运行的时候,有时会出现线程安全问题 例如:买票程序,有可能会出现不同窗口买同一张编号的票

770
来自专栏好好学java的技术栈

java基础提升篇:synchronized同步块和volatile同步变量

822
来自专栏我和PYTHON有个约会

13.1 函数中的变量

在函数中,我们可以看到也进行了变量的使用,那函数中的变量和函数外的变量到底有什么区别呢?

722

扫码关注云+社区

领取腾讯云代金券