力扣349 - 两个数组的交集【哈希表+数组+双指针】

简介: 对应力扣349.两个数组的交集,三种思路三个方向,带你玩转LeetCode

一、题目描述及思路讲解

1. 题目描述

原题传送门
给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的

提示:

1 <= nums1.length, nums2.length <= 1000
  0 <= nums1[i], nums2[i] <= 1000

2. 思路顺理和分析

  • 题目意思很简单,就是给你两个数组,然后求他们的交集,也就是相同的元素。首先我们应该考虑要使用那种数据结构,可以看到,之前的题解都是没有贴上数据范围的,这题我在题目描述的时候加上了一个提示,也就是两个数组的数据范围,因为这个数据范围是力扣官方近期修改后的数据,原本这个数据是比较大的,我也不太记得了,之前做的时候是10^9^,但是从现在的数据范围可以看出,只是1 - 1000这样的范围,其实这个在力扣的题目中还是比较小的数据,因为关注到了这一点,因此我又想出了一种方案,一开始用的是==哈希表==解决,因为考虑到数据比较大,但是现在数据范围改小了,因此考虑==数组==会比较适合一些,然后我就根据数组又萌生出了一种==双指针==的思路,也是比较巧妙的一种方法,因此作为经典题型分享给大家:raised_hands:

二、方法罗列及步骤详解

方法一【哈希表】

结构选择与分析

对于给你一个元素,去判断在这个集合里是否出现过,这种题型,都应该第一时间想到哈希表,因为其实最搞笑的,接着既然是求解集合相关的问题,那就想到set,但是有关set的哈希结构有三种

集合 底层实现 是否有序 是否可重复 数值可否更改 查询效率 增删效率
std::set 红黑树 有序 O(nlogn) O(nlogn)
std::multiset 红黑树 有序 O(nlogn) O(nlogn)
std::unordered_set 哈希表 无序 O(1) O(1)
set和multiset底层实现都是 红黑树,unordered_set的底层实现是 哈希表, 使用unordered_set 读写效率是最高的,并不需要对数据进行排序,而且还不要让数据重复,所以选择unordered_set,具体的详解如何选择哈希结构我在 一文带你快速入门【哈希表】中有详解介绍过,如果不太清楚的小伙伴可以再去看看:runner:
  • 具体的思路就是将题目给出的nums1放到哈希集合unordered_set中,然后去遍历nums2这个数组,看看在nums2中是否有我们之前存在哈希集合中的相同的数,为了更加生动地理解,特此画了张逻辑图给大家看,可以看出,在转化为unordered_set是自动进行了去重操作,因为集合存在一个互异性的原理,一个集合中不可以有重复的元素,因此用此哈希结构都不需要我们手动进行去重操作

请添加图片描述

  • 讲解完具体思路后,C++代码如下
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> num(nums1.begin(),nums1.end());    //把nums1中数放入num集合

        //遍历nums2数组,与num集合做比较
        for(int i : nums2)
        {
            if(num.find(i) != num.end())
                //没有到num的结尾就发现了异常情况
                result.insert(i);   //将交集元素放入result集合
        }
        //最后以一个vector容器的形式返回
        return vector<int>(result.begin(),result.end());
    }
};
  • num是暂时存放nums1的集合,result是存放结果集的,然后在对nums2进行遍历的时候,用find()函数去寻找是否有符合条件的元素,若是没到结尾便发现了有相同元素,那此元素即为交集,insert()进result结果集中,最后要开辟一个vector容器去返回结果,将result的开始迭代器和结束迭代器传入即可
此题的提交结果
请添加图片描述

方法二【数组】

  • :star:开头提到,因为官方修改了数据范围,因此考虑到使用数组更为优化。逻辑思路还是类似,首先要定义一个大小大于1000的数组大小值,==将里面的数据都初始化为0,这点很重要==,否则初始化的数据会是随机值,会影响最后的结果输出然后通过循环先去遍历nums1,将出现过的数所对应的数组都置为1,接着就是去遍历nums2,判断是否有相等的数字,若是有,则将其放入哈希集合中,最后还是一样定义一个vector容器返回即可
  • 具体C++代码如下
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        int hash[1004]{};     //采取数组存储
        for(int i : nums1)
            hash[i] = 1;
        for(int j : nums2)
            if(hash[j] == 1)
                result.insert(j);
        
        return vector<int>(result.begin(),result.end());
    }
};
这是数组解法的通过效率,可以看出空间复杂度低了许多

请添加图片描述

方法三【双指针】

  • 最后一个方法也是我根据数组萌生出来的一个方法,那就是利用双指针的思路,虽然效率不是很高,但也是一种思路,值得一试:dizzy:
  • 具体的思路就是先要手动把两个数组排个序,然后定义两个分别指向各自数组的指针,去一个个迭代遍历,可见快排sort()的时间复杂度为O(nlogn),已经需要一部分的时间,所以效率不会太高,但是不需要哈希表去维护数组和集合,也算是省去了一些空间,因为空间与时间是不可兼得的,很少有这样的解法

具体遍历过程

由于动画太快了,因此我一步步分开细讲:mag:
  • 首先就是初始化时的样子

请添加图片描述

  • 当两个值相等时,此数就为待插元素,就判断若还没到达结尾或者此数是否与上一个放入结果集中的数一样,如果都不符合,就讲此数放入结果集,然后两个指针后移,此时4 < 5,故index2后移

请添加图片描述

  • 当碰到两个数不一样时,就判断是n1大还是n2大,比较完后较小数字的指针后移一位

请添加图片描述

  • 此时5 < 8比较小,index1后移

请添加图片描述
。。。

  • 遍历到此处时,由于两数相同,既没有到结果集末尾,上一个结果集中的数又不是9,因此将9放入结果集中

请添加图片描述

  • 最后,当其中任意一指针超过当前数组长度时,便退出循环,返回结果集

请添加图片描述

  • 以下是C++代码展示
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //对两个数组进行排序
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());

        int index1 = 0,index2 = 0;      //指向两个数组的指针
        int l1 = nums1.size();
        int l2 = nums2.size();          //获取两数组的长度
        vector<int> result;
        while(index1 < l1 && index2 < l2)
        {      //index1、index2从0开始,因此不能遍历到l1和l2,否则会造成数组越界
            int n1 = nums1[index1];
            int n2 = nums2[index2];
            if(n1 == n2){
                if(!result.size() || n1 != result.back()){
                    //若还没到结果集结尾或者与上一个插入的容器中的值不同
                    result.push_back(n1);
                }
                index1++;
                index2++;       //双指针的共同后移
            }else if(n1 < n2){
                index1++;
            }else{
                index2++;
            }
        }
        return result;
    }
};
本题的通过效率

请添加图片描述

三、归纳总结与拓展

看完了此题的三种解法后,你是否又多了几种解题的思路呢,本题是哈希表章节中比较经典的题目,虽然并不是很难,但是想要有一个最优解却不易,以下也是哈希表相关的例题,大家在学习了哈希表的基础知识后多去刷刷题,对知识的理解会更加深刻,关注我,后续会有更精彩的题解奉上:boom:

1.两数之和
15. 三数之和
18. 四数之和
202. 快乐数
242.有效的字母异位词

以下是我开创的社区,感兴趣的小伙伴们可以加入进来一起交流学习,解决编程的难题

我的社区::fire:烈火神盾:fire:

相关文章
|
23天前
使用指针访问数组元素
【10月更文挑战第30天】使用指针访问数组元素。
31 3
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
40 0
|
23天前
使用指针访问数组元素
【10月更文挑战第31天】使用指针访问数组元素。
32 2
|
1月前
|
算法 索引
单链表题+数组题(快慢指针和左右指针)
单链表题+数组题(快慢指针和左右指针)
34 1
|
2月前
|
存储
如何使用指针数组来实现动态二维数组
指针数组可以用来实现动态二维数组。首先,定义一个指向指针的指针变量,并使用 `malloc` 为它分配内存,然后为每个子数组分配内存。通过这种方式,可以灵活地创建和管理不同大小的二维数组。
|
2月前
|
存储
如何通过指针数组来实现二维数组?
介绍了二维数组和指针数组的概念及其区别,详细讲解了如何使用指针数组模拟二维数组,包括定义与分配内存、访问和赋值元素、以及正确释放内存的步骤,适用于需要动态处理二维数据的场景。
|
2月前
|
存储 算法 C语言
C语言:什么是指针数组,它有什么用
指针数组是C语言中一种特殊的数据结构,每个元素都是一个指针。它用于存储多个内存地址,方便对多个变量或数组进行操作,常用于字符串处理、动态内存分配等场景。
|
2月前
魔法指针 之 二级指针 指针数组
魔法指针 之 二级指针 指针数组
19 1
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)