Li Kou daily question - day 18 -350 Intersection of two data Ⅱ

2022.6.10 Did you brush the questions today ？

---

subject ：

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 .

analysis ：

In the given two arrays , Find the intersection of these two arrays , The situation may be as follows ：

num1【】=【1,1,2,3】   nums2【】=【1,1,1,4,5】

result ：【1,1】

num1【】=【1,1,1,1,2,3】   nums2【】=【1,1,1,4,5】

result ：【1,1,1】

num1【】=【1,2,3】   nums2【】=【1,1,1,2,3】

result ：【1,2,3】

So the idea of this topic is , Let's start with one nums In the map Inside , And record the number of times for each value , Next we iterate over another array , And judge that these numbers are map Is there... In it , If there is , Save in vector Inside , And times -1

here -1 Operation is to ensure the first one above , Occurrence of the second case , By subtraction -1, It can ensure the minimum number of repetitions

analysis ：

1. Hashtable

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int>map1;
        //unordered_map<int, int>map2;
        vector<int>v1;
        for (auto num : nums1)
        {
            map1[num]++;
        }
        for (auto num : nums2)
        {
           // map2[num]++;
            if (map1[num] !=0)
            {
                map1[num]--;
                v1.push_back(num);
            }
        }
        return v1;
    }
};

2. Double pointer

The idea here is , Use two pointers to point to two arrays respectively , If 1 The value of the pointer is less than 2 Pointer value , that 1 The pointer ++, conversely 2 The pointer ++, When ,1,2 When the values pointed to by the pointer are equal , Insert the value vector in , then 1,2, All hands ++

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int>vec;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int length1 = nums1.size();
        int length2 = nums2.size();
        int index1 = 0;
        int index2 = 0;
        while (index1 < length1 && index2 < length2)
        {
            if (nums1[index1] < nums2[index2])
            {
                index1++;
            }
            else if (nums1[index1] > nums2[index2])
            {
                index2++;
            }
            else
            {
                vec.push_back(nums1[index1]);
                index1++;
                index2++;
            }
        }
        return vec;
    }
};