leetcode-350-Intersection of Two Arrays II（求两个数组的交集）

chenjx85

发布于 2019-03-14 17:13:51

6870

发布于 2019-03-14 17:13:51

文章被收录于专栏：chenjx85的技术专栏

题目描述：

Given two arrays, write a function to compute their intersection.

Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

要完成的函数：

vector<int> intersect(vector<int>& nums1, vector<int>& nums2)

说明：

1、这道题给定两个vector，要求返回两个vector的交集，比如nums1=[1,2,2,1]，nums2=[2,2]，返回的交集是[2,2]，其中有多少个相同的元素就返回多少个。返回的交集不讲究顺序。

2、这道题看完题意，熟悉leetcode的同学应该会马上想到先排序，排序之后的两个vector来比较，时间复杂度会下降很多。

如果不排序，那就是双重循环的做法，O(n^2)，时间复杂度太高了。

先排序再比较的做法，代码如下：（附详解）

    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) 
    {
        sort(nums1.begin(),nums1.end());//给nums1排序，升序
        sort(nums2.begin(),nums2.end());//给nums2排序，升序
        int s1=nums1.size(),s2=nums2.size(),i=0,j=0;//i表示nums1元素的位置，j表示nums2元素的位置
        vector<int>res;//存储最后结果的vector
        while(i<s1&&j<s2)//两个vector一旦有一个遍历完了，那么就结束比较
        {
            if(nums1[i]<nums2[j])
            {
                while(nums1[i]<nums2[j]&&i<s1)//一直找，直到nums1[i]>=nums2[j]
                    i++;
                if(i==s1)//如果i已经到了nums1的外面，那么结束比较
                    break;
            }
            else if(nums1[i]>nums2[j])
            {
                while(nums1[i]>nums2[j]&&j<s2)//一直找，直到nums2[j]>=nums1[i]
                    j++;
                if(j==s2)//如果j已经到了nums2的外面，那么结束比较
                    break;
            }
            if(nums1[i]==nums2[j])//如果刚好相等，那么插入到res中，更新i和j的值
            {
                res.push_back(nums1[i]);
                i++;
                j++;
            }
        }
        return res;
    }

上述代码实测7ms，beats 98.05% of cpp submissions。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-06-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

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

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

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度