平武建站

c++如何解决两个数组的交集问题

这篇文章主要为大家展示了“c++如何解决两个数组的交集问题”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“c++如何解决两个数组的交集问题”这篇文章吧。

网站建设公司,为您提供网站建设,网站制作,网页设计及定制网站建设服务,专注于成都定制网页设计,高端网页制作,对成都岗亭等多个行业拥有丰富的网站建设经验的网站建设公司。专业网站设计,网站优化推广哪家好,专业营销推广优化,H5建站,响应式网站。

一、题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2,2]示例 2:输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[4,9]说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

二、解题思路

(1) 哈希表查找

解题思路：

  • 用哈希表记录一个数组中每个元素出现的次数，myMap{元素：元素出现次数}

  • 遍历另一个数组，当哈希表中存在当前元素时，则对应元素的计数减1，并将该元素存入res中。

C++实现如下：

class Solution {
   
   
   public:vector intersect(vector& nums1, vector& nums2) {
   
   
   if(nums1.empty() || nums2.empty()) return{
   
   
   };// 哈希表记录集合中每个元素出现的次数unordered_map myMap;for( auto &num : nums1 ) myMap[num]++;
        vector res;// 遍历数组2for( int i = 0; i < nums2.size(); ++i ){
   
   
   // 判断数组2和集合1是否有公共元素if( myMap.count(nums2[i]) ){
   
   
   // 找到后，则对应的元素次数减1if( myMap[nums2[i]] > 0 )res.emplace_back(nums2[i]);// 减少集合1中该数的次数myMap[nums2[i]]--;}}return res;}};

运行结果：
c++如何解决两个数组的交集问题
复杂度分析：

  • 时间复杂度：使用了两个for()循环，且是前后关系，因此整体的时间复杂度是O(n+m)，其中 m 和 n 分别是两个数组的长度

  • 空间复杂度：新定义了一个集合myMap来存储数组nums1中的元素，所以空间复杂度也是O(n)或O(m)

(2) 排序+双指针

解题思路：

  • 首先对两个数组进行排序，然后使用两个指针遍历两个数组

  • 初始时，两个指针分别指向两个数组的头部，每次比较两个指针指向的两个数组中的数字

  • 如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。

  • 当至少有一个指针超出数组范围时，遍历结束。

C++实现如下：

class Solution {
   
   
   public:vector intersect(vector& nums1, vector& nums2) {
   
   
   //排序sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());//获取数组长度int len1 = nums1.size();int len2 = nums2.size();//初始指针int index1=0, index2=0;vector res;while(index1 nums2[index2])index2++;//如果元素值大小相同，则双指针都向后移动一位，且将当前值存入reselse{
   
   
   res.push_back(nums1[index1]);index1++;index2++;}}return res;}};

运行结果：
c++如何解决两个数组的交集问题
复杂度分析：

  • 时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 O(mlogm+nlogn)，遍历两个数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。

  • 空间复杂度：除了输出的数组res，没有创建额外的中间数组，空间复杂度为O(1)

以上是“c++如何解决两个数组的交集问题”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！


分享文章：c++如何解决两个数组的交集问题
URL网址：http://pwwzsj.com/article/pdcosh.html

其他资讯