【每日一题】数组系列(2) —— 两个数组的交集

写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我热爱AI、热爱分享、热爱开源！ 这博客是我对学习的一点总结与记录。如果您也对 深度学习、机器视觉、算法、Python、C++ 感兴趣，可以关注我的动态，我们一起学习，一起进步~
我的博客地址为：【AI 菌】的博客
我的Github项目地址是：【AI 菌】的Github

链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
来源：力扣（LeetCode）

一、题目描述

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

示例 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
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

二、解题思路

(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; // 遍历数组2 for( int i = 0; i < nums2.size(); ++i ){ // 判断数组2和集合1是否有公共元素 if( myMap.count(nums2[i]) ){ // 找到后，则对应的元素次数减1 if( myMap[nums2[i]] > 0 ) res.emplace_back(nums2[i]); // 减少集合1中该数的次数 myMap[nums2[i]]--; } } return res; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

运行结果：

复杂度分析：

• 时间复杂度：使用了两个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++; //如果元素值大小相同，则双指针都向后移动一位，且将当前值存入res else{ res.push_back(nums1[index1]); index1++; index2++; } } return res; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

运行结果：

复杂度分析：

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

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

由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！

推荐文章

• 【C++21天养成计划】不聊学习只谈干货（Day1）
• 【人生苦短，我学 Python】序言——不学点Python你就out了？
• TF2.0深度学习实战（一）：分类问题之手写数字识别

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/114634447