每天一算:Intersection of Two Arrays

每天一算:Intersection of Two Arrays

leetcode上第349号问题:Intersection of Two Arrays

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

示例 1:  
输入: nums1 = [1,2,2,1], nums2 = [2,2]  
输出: [2]

示例 2:  
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]  
输出: [9,4]

说明:

  • 输出结果中的每个元素一定是唯一的。  

  • 我们可以不考虑输出结果的顺序。

思路

容器类set的使用。

  • 遍历num1,通过set容器record存储num1的元素;

  • 遍历num2,在record中查找是否有相同的元素,如果有,用set容器resultSet进行存储;

  • 将resultSet转换为vector类型。

动画演示

每天一算:Intersection of Two Arrays

代码一

 1// 349. Intersection of Two Arrays
2// https://leetcode.com/problems/intersection-of-two-arrays/description/
3// 时间复杂度: O(nlogn)
4// 空间复杂度: O(n)
5class Solution {
6public:
7    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
8
9        set<int> record;
10        forint i = 0 ; i < nums1.size() ; i ++ ){
11            record.insert(nums1[i]);
12        }
13
14        set<int> resultSet;
15        forint i = 0 ; i < nums2.size() ; i ++ ){
16            if(record.find(nums2[i]) != record.end()){
17                resultSet.insert(nums2[i]);
18            }
19        }
20
21        vector<int> resultVector;
22        for(set<int>::iterator iter = resultSet.begin(); iter != resultSet.end(); iter ++ ){
23            resultVector.push_back(*iter);
24        }
25
26        return resultVector;
27    }
28};

代码二

 1// 349. Intersection of Two Arrays
2// https://leetcode.com/problems/intersection-of-two-arrays/description/
3// 时间复杂度: O(nlogn)
4// 空间复杂度: O(n)
5class Solution {
6public:
7    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
8
9        set<int> record(nums1.begin(), nums1.end());
10
11        set<int> resultSet;
12        forint i = 0 ; i < nums2.size() ; i ++ )
13            if( record.find(nums2[i]) != record.end() )
14                resultSet.insert( nums2[i] );
15
16        return vector<int>(resultSet.begin(), resultSet.end());
17    }
18};

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 每天一算:Intersection of Two Arrays

我还会在以下平台发布内容

GitHub 哔哩哔哩