力扣每日一题-第18天-350.两个数据的交集Ⅱ

2022.6.10今天你刷题了吗？

---

题目：

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

分析：

在给定的两个数组中，求出这两个数组的交集，存在的情况可能如下：

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

结果：【1，1】

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

结果：【1，1，1】

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

结果：【1，2，3】

因此本题思路在于，先把一个nums放进map里面，并且记录每个值的次数，接下来我们遍历另外一个数组，并且判断这些数在map里面是否存在，如果存在，则存进vector里面，并且次数-1

这里-1操作是保证上面第一种，第二种情况的出现，通过减-1，可以保证取到最少的重复次数

解析：

1.哈希表

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.双指针

这里的思路是，利用两个指针分别指向两个数组，如果1指针的值小于2指针的值，那么1指针++，反之2指针++，当，1，2指针指向的值相等时，把该值插入vector中，然后1，2，指针都++

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;
    }
};