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

蔚落 2022-11-06 15:55 146阅读 0赞

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

解题思路：

*  用哈希表记录一个数组中每个元素出现的次数，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;
        }
    };

运行结果：  
![在这里插入图片描述][20210310144756815.png]  
复杂度分析：

*  时间复杂度：使用了两个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;
        }
    };

运行结果：  
![在这里插入图片描述][20210310152029849.png]  
复杂度分析：

*  时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 O(mlogm+nlogn)，遍历两个数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。
 *  空间复杂度：除了输出的数组res，没有创建额外的中间数组，空间复杂度为O(1)

--------------------

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

![在这里插入图片描述][2020090613542669.png_pic_center]  
***推荐文章***

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

[AI]: https://blog.csdn.net/wjinjie
[AI _Github]: https://github.com/Keyird/DeepLearning-TensorFlow2.0
[20210310144756815.png]: /images/20221023/4680860bb6854bb1a2d4b0246795ddef.png
[20210310152029849.png]: /images/20221023/a2de6ef1678c4921b1788d6dff879519.png
[2020090613542669.png_pic_center]: /images/20221023/4367d5d2cc3b48289b204e6879dd4cb9.png
[C_21_Day1]: https://blog.csdn.net/wjinjie/article/details/105316043
[Python_Python_out]: https://ai-wx.blog.csdn.net/article/details/110674503
[TF2.0]: https://ai-wx.blog.csdn.net/article/details/104700834