349. 两个数组的交集
时间:2020年11月2日
知识点:数组、哈希表
题目链接:
https://leetcode-cn.com/problems/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]
说明
:
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
解法
:
- 运用c++库函数 unordered_set 存放数据,取出容量小的set中数据 查看再另一个set中是否存在
- 对两个数组排序,两个指针移动,并判断放入的数组是否重复
代码
#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> ans;
unordered_set<int> n1(nums1.begin(),nums1.end());
unordered_set<int> n2(nums2.begin(),nums2.end());
for (auto x:n1){
if(n2.count(x))
ans.push_back(x);
}
return ans;
}
};
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int length1 = nums1.size(), length2 = nums2.size();
int index1 = 0, index2 = 0;
vector<int> ans;
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2) {
// 保证加入元素的唯一性
if (!ans.size() || num1 != ans.back()) {
ans.push_back(num1);
}
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return ans;
}
};
int main()
{
vector<int> num1{1,2,2,1};
vector<int> num2{2,2};
Solution s;
vector<int> ans = s.intersection(num1, num2);
for(int x: ans)
cout<<x<<endl;
return 0;
}
今天也是爱zz的一天哦!
版权声明:本文为qq_30031221原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。