Leetcode--Intersection of Two Arrays

发表于   |   分类于   |     |   阅读次数

本题的题意

给定两个数组，求数组的交集。

思路：假如有数组A，B，那么可以遍历数组B的元素，查看是否有在A中出现，如果有，就是交集中的一个元素。
注意点：
1、如果B中的某个元素是交集中的元素，且该元素在B中重复出现，就不要再讲其放入到交集中了，因为交集中的元素要保证唯一性。
可以采用std::set，先将A，B中重复的元素提前过滤掉，再讲B中元素一次插入到A中，如果插入失败，说明此元素是交集中的一元。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		set<int> h1;//过滤A中重复的元素
		for(int i=0; i<nums1.size(); ++i)
			h1.insert(nums1[i]);
		set<int> h2;//过滤B中重复的元素
		for (int i=0; i<nums2.size(); ++i)
			h2.insert(nums2[i]);
		vector<int>r;
		set<int>::iterator it = h2.begin();
		while(it != h2.end())//求交集
		{
			if(!h1.insert(*it).second)
				r.push_back(*it);
			it++;
		}
		return r;
	}
};