leetCode350.IntersectionofTwoArraysII哈希

350. Intersection of Two Arrays II

成都创新互联专业为企业提供郊区网站建设、郊区做网站、郊区网站设计、郊区网站制作等企业网站建设、网页设计与制作、郊区企业网站模板建站服务,十载郊区做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。

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?

题目大意:

找出两个数组中相同元素,相同元素的个数可以大于1.

思路:

将数组2的元素放入multiset中。

遍历数组1,如果在multiset找到与数组1相等的元素,将该元素放入结果数组中,在multiset中删除第一个和这个元素相当的元素。

代码如下:

class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        vector result;
        multiset set2;
        for(int i = 0; i < nums2.size(); i++)
            set2.insert(nums2[i]);
        for(int i = 0; i < nums1.size(); i++)
        {
            if(set2.find(nums1[i]) != set2.end())
            {
                result.push_back(nums1[i]);
                set2.erase(set2.find(nums1[i]));
            }
        }
        return result;
    }
};

2016-08-13 14:03:35


网站名称:leetCode350.IntersectionofTwoArraysII哈希
网址分享:http://myzitong.com/article/ijspid.html