湖南网站建设哪家专业,网站建设工作量评估报价表,wordpress产品插件,网站建设图片素材题目描述
给定两个数组 nums1 和 nums2 #xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1#xff1a;
输入#xff1a;nums1 [1,2,2,1], nums2 [2,2]
输出#xff1a;[2]示例 2#xff1a;
输入#xf…题目描述
给定两个数组 nums1 和 nums2 返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1
输入nums1 [1,2,2,1], nums2 [2,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分析思路
方法1cpp中关于set有三种分别是set、unordered-set和multi-set其中set和multi-set底层使用红黑树来实现的unordered-set的底层是用哈希映射值来存储的。unordered-set在映射的时候效率是最高的因此选择使用unordered-set而且它本身是会去重的。
此题中我们用unordered_set来进行实现 首先把num1变成set
然后遍历num2如果2中的元素在set中出现过代码中nums1_set.find(num)!num1_set.end()表示的是找到了这个数则插入到res中
find()函数返回一个迭代器指向范围内搜索元素的第一次出现。
如果没有找到目标元素则返回last即查找范围的结尾。在这个例子中last就是v.end()。
因此如果it ! v.end()则说明find()函数找到了目标元素否则说明没有找到目标元素。最后返回vector形式的结果。
cpp代码如下
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint res; // 存放结果用set自动去重了。unordered_setint nums1_set(nums1.begin(), nums1.end()); // 使用哈希表把nums1数组变成setfor(int num:nums2){// 如果在set中找到了num则将num插入到res中。if(nums1_set.find(num)!nums1_set.end()){ // 注意语法是这样写的res.insert(num);}}return vectorint(res.begin(), res.end());}
};方法2由于题中限制了数组大小不超过1000因此也可以使用数组的哈希法进行求解。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {int hash[1005] {0};unordered_setint res;for(int i0;inums1.size();i){// 存在过这个值就把hash数组的值变为1hash[nums1[i]] 1;}for(int i0;inums2.size();i){// 如果等于1了说明重复insert到res中if(hash[nums2[i]] 1){res.insert(nums2[i]);}}return vectorint(res.begin(), res.end());}
};
