【 LeetCode 】 350. The intersection of two arrays. II

题目

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

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

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

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小,哪种方法更优？
如果 nums2的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办？

题解

使用哈希表（unordered_map）Stores the value and the number of occurrences of one of the arrays,Then find and compare one by one

//C++
class Solution {
    
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    
        if(nums1.size() > nums2.size())//nums1存入哈希表中,Lookup is faster when the number of stores is small
            return intersect(nums2,nums1);

        unordered_map<int,int> mynums;//哈希表
        //将nums1存入表中
        for(int k:nums1)
        {
    
            mynums[k]++;
        }

        vector<int> result;//存储结果
        //遍历nums2,Record when you meet the conditions
        for(int k:nums2)
        {
    
            if(mynums.count(k) && mynums[k]!=0)
            {
    
                result.push_back(k);
                mynums[k]--;
            }
        }

        return result;
    }
};

先排序,然后使用双指针法

class Solution {
    
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    
    	//排序
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
		
		//存储结果
        vector<int> result;

		//初始化参数
        int i=0;
        int j=0;
        int len1=nums1.size();
        int len2=nums2.size();

		//开始扫描
        while(i<len1 && j<len2)
        {
    
            if(nums1[i]==nums2[j])//Recorded when the values ​​pointed to by the two pointers are equal
            {
    
                result.push_back(nums1[i]);
                i++;
                j++;
            }
            else if(nums1[i]<nums2[j])//When not equal, the pointer with the smaller value is incremented by one,另一个不变
            {
    
                i++;
            }
            else
            {
    
                j++;
            }
        }
        return result;
    }
};