350. Intersection of Two Arrays II
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.
思路:
将数组2的元素放入multiset中。
遍历数组1,如果在multiset找到与数组1相等的元素,将该元素放入结果数组中,在multiset中删除第一个和这个元素相当的元素。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class
Solution {
public
:
vector<
int
> intersect(vector<
int
>& nums1, vector<
int
>& nums2) {
vector<
int
> result;
multiset<
int
> set2;
for
(
int
i = 0; i < nums2.size(); i++)
set2.insert(nums2[i]);
for
(
int
i = 0; i < nums1.size(); i++)
{
if
(set2.find(nums1[i]) != set2.end())
{
result.push_back(nums1[i]);
set2.erase(set2.find(nums1[i]));
}
}
return
result;
}
};
|
本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1837559