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

相关文章

  • 548. 两数组的交 II 排序+双指针

    样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

    和蔼的zhxing
  • 181. 将整数A转换为B

    如果要将整数A转换为B,需要改变多少个bit位? 如: 如把31转换为14,需要改变2个bit位。

    和蔼的zhxing
  • opencv小项目练习之数独求解

    对于给定的数独照片(尽可能干净整齐),进行一系列处理,提取位置和数字信息,这中间可能要用到一系列图像处理的基本算法,数字识别时初步打算用knn来做,knn对手写...

    和蔼的zhxing
  • Array - 88. Merge Sorted Array

    Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one s...

    用户5705150
  • 【LeetCode】88. 合并两个有序数组 双指针

    给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

    韩旭051
  • leetcode-88-Merge Sorted Array

    Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one s...

    chenjx85
  • 【LeetCode】 两个数组的交集

    韩旭051
  • [WPF]为什么使用SaveFileDialog创建文件需要删除权限?

    好像很少人会遇到这种需求。假设有一个文件夹,用户有几乎所有权限,但没有删除的权限,如下图所示:

    dino.c
  • 设置一个计划任务,到了时间就运行代码

    其实这篇文章的内容很简单,说白了就是设置一个计划任务,当触发到设定的条件后就运行。

    伪君子
  • 双指针问题-LeetCode 88、125(双指针,大小写转换)

    给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券