Force buckle 349 Intersection of two arrays

Given two arrays  nums1  and  nums2 , return   Their intersection  . Every element in the output must be   only   Of . We can   Regardless of the order of the output results  .

Special attention required ： Each element of the output must be unique , That is, the output is de duplicated , At the same time, the order does not need to be considered

Using arrays to do hashing , Because the problem limits the size of the value , This question does not limit the number of occurrences of each element , So you don't have to use arrays .

And if the hash is small , Very scattered 、 The span is very large , Using arrays can be a huge waste of space .

Now it's time to use another structure ,set , About set,C++ We provide the following three kinds of data structures ：

• std::set
• std::multiset
• std::unordered_set

std::set and std::multiset The underlying implementations are all red black trees ,std::unordered_set The underlying implementation of is a hash table , Use unordered_set Reading and writing efficiency is the highest , There's no need to sort the data , And don't duplicate the data , So choose unordered_set.

  The idea is shown in the picture ：

  Method ：unordered_set

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // Store the returned results 
        unordered_set<int> result_set;
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for(int num : nums2) {
            // Find out nums2 The elements in nums1 in , Record the element in the returned result set 
            if(nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        // Note that what you need to return here is an array 
        return vector<int>(result_set.begin(), result_set.end());
    }
};