[LeetCode]349. Intersection of Two Arrays 两个数组的交集

题目地址:

https://leetcode.com/problems/intersection-of-two-arrays/

题目描述:

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

题目大意:

给你两个数组,写一个函数来计算它们的交集。

例子:

给你  nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回  [2].


之前写过一题 Single Number III 这题很有意思的一点就是它运用了哈希容器 unordered_map 来进行存储与查找。那么这题一样也可以用无序 Map 去做。只需要写两张表,然后用一张表来对另一张表进行 find( )的寻找即可。

这是我的代码。算法挺简单的就不过多介绍了。不过我不能总是依靠哈希容器无序 Map 去做查找。

“(引用) 答案地址:http://www.cnblogs.com/grandyang/p/5507129.html

这道题让我们找两个数组相同的部分,难度不算大,我们可以用个set把nums1都放进去,然后遍历nums2的元素,如果在set中存在,说明是公共部分,加入结果的set中,最后再把结果转为vector的形式即可:

解法一:

我们还可以使用两个指针来做,先给两个数组排序,然后用两个指针分别指向两个数组的开头,然后比较两个数组的大小,把小的数字的指针向后移,如果两个指针指的数字相等,那么看结果res是否为空,如果为空或者是最后一个数字和当前数字不等的话,将该数字加入结果res中,参见代码如下:

解法二:

我们还可以使用二分查找法来做,思路是将一个数组排序,然后遍历另一个数组,把遍历到的每个数字在排序号的数组中用二分查找法搜索,如果能找到则放入结果set中,这里我们用到了set的去重复的特性,最后我们将set转为vector即可:

解法三:

或者我们也可以使用STL的set_intersection函数来找出共同元素,很方便:

解法四:

现在越来越觉得 for 循环遍历查找开销很大,应该学会使用一些封装好的东西。比如上面的 set 方法就特别好用。