[OJ] intersection of two arrays (set, hash mapping...)

OJ - Intersection of two arrays

questions ： Simple

OJ link ：349. Intersection of two arrays - Power button （LeetCode） (leetcode-cn.com)

Title Description ：

Given two arrays nums1 and nums2 , Return their intersection . Every element in the output must be only Of . We can ignore the order of output results .

Example 1：

Input ：nums1 = [1,2,2,1], nums2 = [2,2]

Output ：[2]

Example 2：

Input ：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output ：[9,4]

explain ：[4,9] It is also passable

---

Solution 1 ：set duplicate removal

class Solution {
    
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    
        vector<int> res;
        
        //  use unordered_set De duplication of elements in two arrays 
        unordered_set<int> s1(nums1.begin(), nums1.end());
        unordered_set<int> s2(nums2.begin(), nums2.end());

        //  Traverse s1, In turn, it's s2 Find if there is s1 The elements in 
        for (auto& e : s1) {
    
            if (s2.find(e) != s2.end()) res.push_back(e);
        }

        return res;
    }
};

Solution 2 ： Hash map

class Solution {
    
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    
        vector<int> res;

        //  hold nums1 All elements are mapped to the hash table 
        int hash[1001] = {
     0 };
        for (auto& e : nums1) hash[e]++;

        //  Traverse nums2, Check the hash table for nums2 The elements in , If hash[i] Greater than 0, Intersection 
        for (auto& e : nums2) {
    
            if (hash[e] > 0) {
    
                res.push_back(e);
                hash[e] = 0; //  Zeroing , prevent nums2 There are repeating elements behind , such as [9,4,9]
            }
        }

        return res;    
    }
};

Solution 3 ： Double pointer after sorting

class Solution {
    
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    
        vector<int> res;

        //  use set An array nums1 and nums2 De duplication and sorting 
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());

        /* nums1 = [4,9,5], nums2 = [9,4,9,8,4] * s1 = 4,5,9 * s2 = 4,8,9 */
        
        //  Double pointer 
        auto it1 = s1.begin(), it2 = s2.begin();
        //  Traverse s1 and s2
        while (it1 != s1.end() && it2 != s2.end()) {
     //  It didn't come to an end 
            //  If the elements pointed to by two iterators are not equal , The small one goes forward ++
            if (*it1 > *it2) it2++;
            else if (*it1 < *it2) it1++;
            else {
    
                res.push_back(*it1); //  intersection 
                it1++, it2++;
            }
        }

        return res;
    }
};

---