安庆市大观区城乡建设局网站,服务器方面如何规划建设网站,wordpress 导航栏在哪,app定制开发大概多少钱求两个数组的交集#xff0c;直白点儿就是【nums2 的元素是否在 nums1 中】。
在一堆数中查找一个数#xff0c;当然是扔出哈希。碰到这种对目前来说是未知数值大小的情况#xff0c;我们可以使用集合 set 来解决。 使用数组来做哈希的题目#xff0c;是因为题目都限制了数…求两个数组的交集直白点儿就是【nums2 的元素是否在 nums1 中】。
在一堆数中查找一个数当然是扔出哈希。碰到这种对目前来说是未知数值大小的情况我们可以使用集合 set 来解决。 使用数组来做哈希的题目是因为题目都限制了数值的大小。 而这道题目没有限制数值的大小就无法使用数组来做哈希表了。 而且如果哈希值比较少、特别分散、跨度非常大使用数组就造成空间的极大浪费。 此时就要使用另一种结构体了set 关于setC 给提供了如下三种可用的数据结构 std::setstd::multisetstd::unordered_set std::set和std::multiset底层实现都是红黑树std::unordered_set的底层实现是哈希表 使用unordered_set 读写效率是最高的并不需要对数据进行排序而且还不要让数据重复所以选择unordered_set。 那有同学可能问了遇到哈希问题我直接都用set不就得了用什么数组啊。 直接使用set 不仅占用空间比数组大而且速度要比数组慢set把数值映射到key上都要做hash计算的。 不要小瞧 这个耗时在数据量大的情况差距是很明显的。 本来想直接将结果存入vector输出、但
如果 nums2 中有重复元素结果 out 中也会包含重复元素。这是因为你在遍历 nums2 时没有对已经找到的重复元素进行处理。
为了确保结果中不包含重复元素可以使用 std::set 来存储结果或者直接在插入结果时检查是否已经存在。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint common(nums1.begin(), nums1.end());setint out;for(int i: nums2){if(common.find(i) ! common.end()){out.insert(i);}}return vectorint(out.begin(), out.end());}
};
同样可以使用unordered_set
或者
out.push_back(num);
common.erase(num); // 从 common 中移除避免重复 力扣修改了题目有了数值范围、可以使用数组了。但如果使用数组、最后存储防止重复还是要使用一下set\多一个删除操作。 用unordered_map来实现
第一步遍历数组 nums1将出现的数作为key存进哈希表中,并将其value赋值为1。
因为【输出结果中的每个元素一定是唯一的】所以对于 key 所对应的 value 来说“数值是多少”就无所谓了所以在本题中不管某个元素在数组中出现多少次我把 value 都置为 1。
遍历 nums2 数组nums2 数组中的元素如果出现在哈希表中则证明是和 nums1 数组相交的元素则加入结果列表中。并将哈希表中对应value赋值为0防止重复加入。
class Solution{
public:vectorint intersection(vectorint nums1, vectorint nums2){unordered_mapint, int hash;vectorint out;for(int i: nums1){if(hash.find(i) hash.end()){hash[i] 1;}}for(int i: nums2){if(hash.find(i) ! hash.end() hash[i] 1){out.push_back(i);hash[i] 0;//防止重复读取}}return out;}
};
