/*问题：计算两个数组的交集(交集中元素与顺序无关，不是指公共子数组)
可以返回重复的数
思考题3：
If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.
*/
/*
* 方法一：hash表
* 过程：构建hash表计数器，依nums2在计数器中出现的次数，如果出现了，就push元素，计数器对应值减一
* 分析：O(m+n),O(m)
*/
#include <unordered_map>
class Solution
{
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
{
unordered_map<int, int> counter;
vector<int> res;
for(int num:nums1) counter[num]++; // 统计每个数的出现次数（首次调用 operator[] 以零初始化计数器
for(int num:nums2)
{
if(counter.find(num) != counter.end() && counter[num]>=1)//如果在nums1中找得到对应元素而且计数值大于1时，说明是交集的一部分
{
counter[num]--;
res.push_back(num);
}
}
return res;
}
};
/*
* 方法二：排序之后再找
以时间换空间
* 分析：O（mlogm +nlogn+m+n），O(1)
*/
#include <algorithm>
class Solution
{
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
{
if(nums1.empty() || nums2.empty()) return {};
vector<int> res;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while(i < nums1.size() && j < nums2.size()) //i，j分别用来遍历两个数组
{
if (nums1[i] < nums2[j]) i++; //递增第一个数组的指针
else if (nums1[i] > nums2[j]) j++; //递增第二个数组的指针
else
{
res.push_back(nums1[i]);
i++; j++; //同时递增两个数组指针
}
}
return res;
}
};
