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

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

一、题目描述

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

示例 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<int> intersect(vector<int>& nums1, vector<int>& nums2) {
   
   
   if(nums1.empty() || nums2.empty()) return{
   
   
   };// 哈希表记录集合中每个元素出现的次数unordered_map<int, int> myMap;for( auto &num : nums1 ) myMap[num]++;
        vector<int> 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;}};

运行结果：

复杂度分析：

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

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

(2) 排序+双指针

解题思路：

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

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

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

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

C++实现如下：

class Solution {
   
   
   public:vector<int> intersect(vector<int>& nums1, vector<int>& 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<int> res;while(index1<len1 && index2<len2){
   
   
   //如果数组1元素<数组2，将数组1的指针向后移动1位if(nums1[index1] < nums2[index2])index1++;//如果数组2元素<数组1，将数组2的指针向后移动1位else if(nums1[index1] > nums2[index2])index2++;//如果元素值大小相同，则双指针都向后移动一位，且将当前值存入reselse{
   
   
   res.push_back(nums1[index1]);index1++;index2++;}}return res;}};

运行结果：

复杂度分析：

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

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

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