Leetcode:349. 两个数组的交集
编辑
18
2024-06-27
Leetcode题目链接:349. 两个数组的交集
题目描述
给定两个数组 nums1
和 nums2
,返回它们的交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
题目示例
示例一
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
示例二
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的
提示
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
解题思路
哈希表(set形式)
使用unordered_set容器定义数组result,用于存放最终的数组交集
使用unordered_set容器定义数组nums,并使用构造方法将nums1数组转换为set,用于后续num2查表
for循环遍历数组nums2,若能在nums集合中找到相应的元素,则该元素为两个集合共有的元素,即交集的组成部分,将其插入到result集合中(set自动去重)
将结果数组result转换为vector形式返回
哈希表(数组形式)
使用unordered_set容器定义数组result,用于存放最终的数组交集
题设条件给出数据元素均小于等于一千,可定义稍大于一千的数组作为哈希表来解决此问题,即 int hash[1005] = {0}(此处将1005个元素均初始化为0,供后续使用)
for循环遍历数组nums1,将hash数组的对应位置元素置1,即该元素在nums1中出现
for循环遍历数组nums2,判断hash数组的对应位置元素是否为1,即nums2中该元素是否在nums1也曾出现过
若出现则向result集合中插入该元素
若无则不执行任何操作
将结果数组result转换为vector形式返回
我的答案
//使用set容器
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
unordered_set<int> nums(nums1.begin(), nums1.end());
for(int num : nums2) {
if(nums.find(num) != nums.end()) {
result.insert(num);
}
}
return vector<int>(result.begin(), result.end());
}
};
//使用数组哈希表
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
int hash[1005] = {0};
for(int num : nums1) {
hash[num] = 1;
}
for(int num : nums2) {
if(hash[num] == 1) {
result.insert(num);
}
}
return vector<int>(result.begin(), result.end());
}
};
提交结果
- 0
- 0
-
赞助
AliPayWeChat Pay -
分享