#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <unordered_set>
#include <set>
using namespace std;
/*
问题:
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.
Follow up:
What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
输入:
2(第一个数组元素个数) 2(第二个数组元素个数)
1 2
1 2
4 2
1 2 2 1
2 2
输出:
1 2
2 2
分析:
假设n为其中一个数组的长度，m为另一个数组的长度
通用方法】此题可以将一个数组的所有元素放入一个multiset,然后读取另一个数组中的元素。
如果存在，就存储到结果集。并删除multiset中该元素一次。set插入，删除，查找时间复杂度为O(logN)，
因为实际上每次插入就是调整堆
时间复杂度为O(NlogN+M*logN)=O((N+M)logN)，因此尽量用长度较小数组作为multiset。
1】如果给定的数组已经排序，采用两个指针index1,index2初始分别指向两个数组，
如果两个指针指向的元素相同，则一起累加，并将该元素存入到结果集
否则，让两个指针中指向较小元素的指针累加，然后继续比较。
总的时间复杂度为O(n+m)
2】如果数组1的长度小于数组2的长度，采用通用解法时将数组1作为multiset中元素。
3】如果数组2的元素存储在磁盘上，内存被限制为不能一次性加载所有元素到内存中。
可以先把数组1的所有元素以哈希map的形式存储在内存中，每次读取数组2中一部分元素进行处理，
直至数组2全部处理完。
关键:
1 注意重复元素出现多少次，就显示多少次，这个应该用multiset
删除的时候删除迭代器，不能删除元素（这样会把所有值等于该元素的全部删除）
*/
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
if(nums1.empty() || nums2.empty())
{
return result;
}
multiset<int> nums(nums1.begin() , nums1.end());
multiset<int> setResult;
int size = nums2.size();
for(int i = 0 ; i < size ; i++)
{
auto iter = nums.find(nums2.at(i));
if(iter != nums.end())
{
setResult.insert(nums2.at(i));
//找到了要删除multiset中的元素，但是这样删除会导致全部删除了,可以先找到该元素的迭代器，删除该迭代器即可
nums.erase(iter);
}
}
result = vector<int>(setResult.begin() , setResult.end());
return result;
}
};
void print(vector<int>& result)
{
if(result.empty())
{
cout << "no result" << endl;
return;
}
int size = result.size();
for(int i = 0 ; i < size ; i++)
{
cout << result.at(i) << " " ;
}
cout << endl;
}
void process()
{
vector<int> nums;
vector<int> nums2;
int value;
int num;
int num2;
Solution solution;
vector<int> result;
while(cin >> num >> num2)
{
nums.clear();
for(int i = 0 ; i < num ; i++)
{
cin >> value;
nums.push_back(value);
}
nums2.clear();
for(int i = 0 ; i < num2 ; i++)
{
cin >> value;
nums2.push_back(value);
}
result = solution.intersect(nums , nums2);
print(result);
}
}
int main(int argc , char* argv[])
{
process();
getchar();
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-500355.html
