【每日leetcode】两个数组的交集II(哈希表)
1 题目描述
2 解决思路
这道题自己想了很久,没有思路。不知道怎么用几行代码解决,那我们的脑子遇到这个问题会怎么想呢?一般会把nums1中的元素一个一个和nums2中的元素比较,发现相同元素的就记一下,继续比较直到所有的元素都比完了。于是我想用两层循环暴力解决,奈何暴力法都写不出来。
于是只能看题解,学到了应用哈希表。思路就是用哈希结构记录nums1中每个元素和元素出现的次数,接着遍历nums2,查找与nums2中的元素相同的哈希表元素(这个元素不仅在哈希表中也有,而且出现次数大于零),每找到一对需要“减少”哈希表中的元素(避免比较了重复元素的问题),用一个动态数组保存查找的结果。
推荐下面这个官方的图解过程,简洁明了,一看就懂。
3 C++代码
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int,int> hashmap; int len1=nums1.size(),len2=nums2.size(); hashmap[nums1[0]]=1; //遍历nums1,记录元素及出现次数 for(int i=1;i<len1;i++){ auto it=hashmap.find(nums1[i]); //哈希表中无nums[i],新增元素 if(it==hashmap.end()){ hashmap[nums1[i]]=1; } //哈希表中已有nums[i],仅增加出现次数 else{ it->second=it->second+1; } } //遍历nums2,记录两数组交集 vector<int> result; int num=0; for(int j=0;j<len2;j++){ //哈希表中有nums[j],rezult增加nums[j],哈希表则减少 auto it=hashmap.find(nums2[j]); if(it!=hashmap.end()&&it->second>0){ result.push_back(nums2[j]); num++; it->second=it->second-1; } } return result; } };