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?
分析
算法1
第一种方法，使用multiset，建立两个set，并且遍历较短的那个nums。这种方法适用于排序和未排序的数组
set的构造时间复杂度 N*log(N)
erase： log(N) + target.count 重复N次，所以erase总时间复杂度 N*log(N)
所以该算法时间复杂度为 N*log(N)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution {public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { multiset<int> set1(nums1.begin(), nums1.end()); multiset<int> set2(nums2.begin(), nums2.end()); vector<int> result; vector<int> & nums = nums1.size() > nums2.size() ? nums2 : nums1;// nums equals to the shorter array for(auto n : nums){ int a = set1.erase(n);// find the count of n in nums1 int b = set2.erase(n);// find the count of n in nums2 if( a && b){ int time = min(a,b); while(time--) result.push_back(n); } } return result; }}; |
算法2
可以使用系统函数 set_intersection求解两个已经排序好的数组的交集
1 2 3 4 5 6 7 8 9 10 11 | class Solution {public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> result(nums1.size() + nums2.size()); sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); auto it = set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), result.begin()); result.resize(it - result.begin()); return result; }}; |
可以自己实现 交集 功能
比如下面的两个排序好的数组，用两个指针分别指向开头，诶个遍历，直到有一个遍历结束
如果 A[i] < B[j]，i++
否则如果 B[j] < A[i]，j++
否则（这里一定是二者相等）push 当前值到 result，并且i++,j++
时间复杂度是O(N+M)
i
A:1 1 2 3 3 4 4 4 4 5
j-
B:0 0 1 1 2 2 4 4 6 result:
i
A:1 1 2 3 3 4 4 4 4 5
j-
B:0 0 1 1 2 2 4 4 6 result:
i-
A:1 1 2 3 3 4 4 4 4 5
j-
B:0 0 1 1 2 2 4 4 6 result:1
i-
A:1 1 2 3 3 4 4 4 4 5
j-
B:0 0 1 1 2 2 4 4 6 result:1,1
i-
A:1 1 2 3 3 4 4 4 4 5
j-
B:0 0 1 1 2 2 4 4 6 result:1,1,2
i
A:1 1 2 3 3 4 4 4 4 5
j-
B:0 0 1 1 2 2 4 4 6 result:1,1,2
i-
A:1 1 2 3 3 4 4 4 4 5
j
B:0 0 1 1 2 2 4 4 6 result:1,1,2
i-
A:1 1 2 3 3 4 4 4 4 5
j
B:0 0 1 1 2 2 4 4 6 result:1,1,2
i-
A:1 1 2 3 3 4 4 4 4 5
j-
B:0 0 1 1 2 2 4 4 6 result:1,1,2,4
i-
A:1 1 2 3 3 4 4 4 4 5
j-
B:0 0 1 1 2 2 4 4 6 result:1,1,2,4,4
i-
A:1 1 2 3 3 4 4 4 4 5
j
B:0 0 1 1 2 2 4 4 6 result:1,1,2,4,4
i-
A:1 1 2 3 3 4 4 4 4 5
j
B:0 0 1 1 2 2 4 4 6 result:1,1,2,4,4
i-
A:1 1 2 3 3 4 4 4 4 5
j
B:0 0 1 1 2 2 4 4 6 result:1,1,2,4,4
i(end)
A:1 1 2 3 3 4 4 4 4 5
j
B:0 0 1 1 2 2 4 4 6 result:1,1,2,4,4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Solution {public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> result(nums1.size() + nums2.size()); int i = 0; sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); auto l1 = nums1.begin(), r1 = nums1.end(); auto l2 = nums2.begin(), r2 = nums2.end(); while(l1 < r1 && l2 < r2){ if(*l1 < *l2){ ++l1; } else if(*l1 > *l2){ ++l2; } else{ result[i++] = *l1; ++l1; ++l2; } } result.resize(i); return result; }}; |
算法3
如果只有nums1可以装进内存，那么可以将nums1放入一个 Hash Table 中，然后读取部分 nums2 到内存，逐个判断并压入result中
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution {public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> mymap; vector<int> result; for(auto n: nums1){ ++mymap[n]; } for(auto n: nums2){ if(mymap[n]-- > 0){ result.push_back(n); } } return result; }}; |
如果nums1和nums2都不能够一次性放在内存中，那么首先对二者进行外部排序，external sort，然后每次读取一部分数据进来，进行算法2，然后不断读取数据