网络建站的费用,一般在什么网站上做电子请帖,济南网站建设排名,商城网站建站数组交集 349. 两个数组的交集排序#xff0b;双指针数组实现哈希表unordered_setunordered_map 350. 两个数组的交集Ⅱ排序 双指针数组实现哈希表unordered_map 349. 两个数组的交集
题目链接#xff1a;349. 两个数组的交集 题目内容如下#xff0c;理解题意#xff1a… 数组交集 349. 两个数组的交集排序双指针数组实现哈希表unordered_setunordered_map 350. 两个数组的交集Ⅱ排序 双指针数组实现哈希表unordered_map 349. 两个数组的交集
题目链接349. 两个数组的交集 题目内容如下理解题意①交集中每个元素是唯一的只能出现一次所以本题要找的是同时出现在数组nums1和nums2中的元素但是并不关心他们出现的次数②输出结果的顺序不用考虑也就是只要找到了同时出现在nums1和nums2中的元素就行可以给数组排序打乱了原本的顺序再去查找、可以用map、set其中key是无序的…… 这个题目暴力求解是可以的暴力求解两层循环将nums1和nums2的元素逐个对比时间复杂度是O(m*n)因为nums1和nums2的长度都1000所以最终也是能够运行的。 考虑更优的解法直接一遍遍历nums1和nums2就好了。以下详述各解法
排序双指针
解法Ⅰ对nums1和nums2排序后从头开始遍历两个数组下标用index1和index2并将nums1[index1] nums2[index2]的元素加入结果数组中。 存在的问题是因为nums1和nums2中存在重复元素如果找到了nums1[index1] nums2[index2]且在nums1中nums1[index1] 有重复即nums1[index11] nums1[index1] 且在nums2中nums2[index2]有重复即nums2[index21] nums2[index2]。那么直接对index和index2会向结果数组中添加重复的元素。 解决找到nums1[index1] nums2[index2]后index1直到找到与之不同的下一个元素就是跳过中间的相同的元素index2同样。
代码实现C
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {vectorint ans;sort(nums1.begin(),nums1.end());//先给nums1和nums2都排序sort(nums2.begin(),nums2.end());//排序后双指针index1和index2遍历nums1和nums2for(int index1 0, index2 0; index1 nums1.size() index2 nums2.size();){if(nums1[index1] nums2[index2]){ans.emplace_back(nums1[index1]); //如果找到在两个数组中出现的元素加入到结果数组中//之后直接跳过和当前元素相同的一截避免有可能向ans中重复添加该元素的可能do{index1;}while(index1 nums1.size() nums1[index1] nums1[index1 - 1]);do{index2;}while(index2 nums2.size() nums2[index2] nums2[index2 - 1]);}//如果不相等更小的那个数向后移同样是跳过和当前元素相同的一截避免重复的比较else if( nums1[index1] nums2[index2]){do{index1;}while(index1 nums1.size() nums1[index1] nums1[index1 - 1]); }else{do{index2;}while(index2 nums2.size() nums2[index2] nums2[index2 -1]); }}return ans;}
};数组实现哈希表
哈希表的好处体现在它能够快速查找一个元素是否存在时间复杂度是O(1)。我们要找nums1和nums2中同时存在的元素换句话——查找nums1中某个元素是否出现在了nums2中。那么就可以用哈希表。因为题目中nums1和num2的长度以及其中的int元素的大小都给了限制1000那么可以用数组来实现哈希表。 直接定义长度为1001的int数组count_1和count_2统计nums1中元素的次数和nums2中元素出现的次数最后对比count_1和count_2的每位元素如果同时不为0的话将对应元素加入到ans中。 代码如下C
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {int count_1[1001] {0}, count_2[1001] {0};vectorint ans;//分别统计nums1和nums2中元素出现情况for ( auto num : nums1){count_1[num]1;}for ( auto num : nums2){ count_2[num];}for ( int i 0; i 1000; i){//在两个数组中出现次数均1时加入ans中if( count_1[i] count_2[i])ans.emplace_back(i);}return ans;}
};优化上面需要用到两个数组count_1和count_2来分别统计nums1、nums2中元素出现的情况之后还要遍历这俩数组。是否有可能只使用一个count数组用两次——遍历nums1的时候出现的元素不统计次数而是count[nums[i]]1标记该元素出现过遍历nums2的时候如果count[nums2[j]] !0就表示在两个数组中同时存在防止重复添加再将count[nums2[j]]0; 代码实现C
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {int count[1001] {0};vectorint ans;//统计nums1中元素的出现情况for ( auto num : nums1){count[num]1;}//遍历nums2for ( auto num : nums2){if(count[num]){ //同时判断nums2中的元素在nums1中是否出现count[num]0;ans.emplace_back(num);}} return ans;}
};unordered_set
题意是要找交集那么直接把数组变成集合然后求两个集合交集就好。实现上将vector变成unordered_set然后对比两个unordered_set的key找到重叠部分。 代码实现C
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {//把vector转化成unordered_setunordered_setint num_set1(nums1.begin(),nums1.end());unordered_setint num_set2(nums2.begin(),nums2.end());vectorint ans;//遍历两个set找交集遍历size小的if( num_set1.size() num_set2.size()){for( auto key : num_set1)if(num_set2.count(key))ans.emplace_back(key);}else{for( auto key :num_set2)if(num_set1.count(key))ans.emplace_back(key);}return ans;}
};unordered_map
最后也能用map来实现遍历nums1和nums2的同时统计其中元素出现的次数用unordered_map来存key是数组中出现的元素value是元素出现的次数 之后找到两个map中重合的key。 代码C
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_mapint,int count_1, count_2; vectorint ans;//用map统计数组中出现的元素及其次数for ( auto num : nums1){count_1[num];}for ( auto num : nums2){count_2[num];}if(count_1.size() count_2.size()){for ( auto key_value : count_1)if(count_2.count(key_value.first))ans.emplace_back(key_value.first);}else{for ( auto key_value : count_2)if(count_1.count(key_value.first))ans.emplace_back(key_value.first);}return ans;}
};350. 两个数组的交集Ⅱ
题目链接350. 两个数组的交集Ⅱ 题目内容 这道题和上一题唯一不同的点在于在nums1和nums2中同时出现的元素如果出现次数不止一次都需要加入到结果中。即不仅要统计同时出现在nums1和nums2中的元素还要统计他们各自出现的次数C1和C2并在结果数组ans中重复min (C1, C2) 次。以下代码均在上一题基础上做一点改动即可。
排序 双指针
排序后数组元素逐个对比就好双指针index1和index2每次对比nums1[index1]和nums2[index2]的关系后直接index1index2 class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {vectorint ans;sort(nums1.begin(),nums1.end());sort(nums2.begin(),nums2.end());for(int index1 0, index2 0; index1 nums1.size() index2 nums2.size();){if(nums1[index1] nums2[index2]){ans.emplace_back(nums1[index1]);//下标直接向后移动这样同时重复出现在两个数组中的元素能够重复添加index1;index2; }else if( nums1[index1] nums2[index2]){index1; }else{index2; }}return ans;}
};
数组实现哈希表
先用数组count统计nums1中出现的元素及其次数再遍历nums2同时出现在nums1中的元素count[nums2[i]]- -向结果数组ans中添加一次该元素。
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {int count[1001] {0};vectorint ans;//统计出现的元素以及次数for ( auto num : nums1){count[num];}for ( auto num : nums2){if(count[num]){//对于同时出现的元素对其次数--保证后续再出现该元素时还能重复添加count[num]--;ans.emplace_back(num);} } return ans;}
};unordered_map
只是将上面的数组换成了unordered_map。用数组实现哈希表适用于nums1和nums2都不大的并且其中元素也不大的情况当数组很大并且数组元素为int大小没有限制的时候用map更合适或者set。 代码如下
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {unordered_mapint,int count;vectorint ans;for(auto num : nums1){count[num];}for(auto num : nums2){if(count.count(num)){ans.emplace_back(num);count[num]--;//如果已经重复添加了min(c1,c2)次了即便后续再出现也不能再添加了if(count[num]0)count.erase(num);}}return ans;}
};
