前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每天一算:Intersection of Two Arrays

每天一算:Intersection of Two Arrays

作者头像
五分钟学算法
发布2018-11-20 15:41:07
3630
发布2018-11-20 15:41:07
举报
文章被收录于专栏:五分钟学算法

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类型。
动画演示
代码一
代码语言:javascript
复制
 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        for( int i = 0 ; i < nums1.size() ; i ++ ){
11            record.insert(nums1[i]);
12        }
13
14        set<int> resultSet;
15        for( int 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};
代码二
代码语言:javascript
复制
 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        for( int 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};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-10-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 思路
  • 动画演示
  • 代码一
  • 代码二
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档