350.Intersection of Two Arrays II

350.Intersection of Two Arrays II

难度:Easy

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
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?

採用map哈希映射，各遍歷一遍即可解決。另外C++也有直接對容器求交集的函數set_intersection. 不過該函數需要注意的前提條件: 需保证第一集合和第二集合有序，并从小到大排序，内部使用默认“<”操作符或者Compare比较元素大小。

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator result);
 
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,

這裏直接用map遍歷了，不用排序：

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        if(nums1.empty() || nums2.empty()) return res;
        unordered_map<int ,int>common;
        for(auto n: nums1)
            common[n]++;
        for(auto n: nums2)
        {
            if(common.count(n) && common[n])
            {
                common[n]--;
                res.push_back(n);
            }
    }
        return res;
    }
};

执行用时 :12 ms, 在所有 C++ 提交中击败了84.82%的用户内存消耗 :9.4 MB, 在所有 C++ 提交中击败了45.43%的用户

Previous349.Intersection of Two Arrays Next367.Valid Perfect Square

Last updated 3 years ago

Was this helpful?

Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] 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?

template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,

class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> res; if(nums1.empty() || nums2.empty()) return res; unordered_map<int ,int>common; for(auto n: nums1) common[n]++; for(auto n: nums2) { if(common.count(n) && common[n]) { common[n]--; res.push_back(n); } } return res; } };