Leetcode notes 350. Intersection of two arrays II

Title Description

Here are two arrays of integers nums1 and nums2 , Please return the intersection of two arrays as an array . Returns the number of occurrences of each element in the result , It should be consistent with the number of occurrences of elements in both arrays （ If the number of occurrences is inconsistent , Then consider taking the smaller value ）. You can ignore the order of the output results .

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]

Tips ：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

Advanced ：

What if the given array has been ordered ？ How will you optimize your algorithm ？
If nums1 Size ratio nums2 Small , Which method is better ？
If nums2 Elements of are stored on disk , Memory is limited , And you can't load all the elements into memory at once , What are you gonna do? ？

Ideas

Because the same number is in vector May appear more than once , So the essence of the topic is , For each number in num1 and num2 Count the number of occurrences , Finally, each number , Take the smallest one . Of course, the traditional violent solution is also possible , But there is no significance of this topic .

Here is the idea of the former , use unordered_map Counting numbers is very effective , Because its underlying implementation is hash surface , So you can $\mathcal{O}(1)$ Check and correct within the time , In fact, in this sense , Arrays are OK, too , But the disadvantage of arrays is , For some extreme numbers , Need to waste a lot of memory , In this sense ,hash The advantages of the table are reflected , Actually use map Such mappings are ok , however map The underlying implementation of is not hash surface , Deposit in it , Need to sort , And this question does not need to be sorted , So the time wasted in sorting is really wasted .

Code

class Solution {
    
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    
        vector<int> ans;
        unordered_map<int, int> temp;// Used to record each number , And where is it nums1 Is the number of times 
        for(int i : nums1)
        {
    
            temp[i] += 1;
        }
        for(int i : nums2)
        {
    
            if(temp[i])
            {
    
                -- temp[i];//nums2 Once in , It's equivalent to using up nums1 One of the numbers 
                ans.push_back(i);
            }
        }
        return ans;
    }
};