LeetCode-350-两个数组的交集-II-Python

350. 两个数组的交加 II


题目起源:力扣(LeetCode)https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

题目


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

示例 1:

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

示例 2:

输出: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入: [4,9]

阐明:

  • 输入后果中每个元素呈现的次数,应与元素在两个数组中呈现的次数统一。
  • 咱们能够不思考输入后果的程序。

进阶:

  • 如果给定的数组曾经排好序呢?你将如何优化你的算法?
  • 如果 nums1 的大小比 nums2 小很多,哪种办法更优?
  • 如果 nums2 的元素存储在磁盘上,磁盘内存是无限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

解题思路


思路:哈希表,双指针

先看题目,联合示例 1 和第一条阐明【输入后果中每个元素呈现的次数,应与元素在两个数组中呈现的次数统一】,由此咱们晓得,同一个数字在两个数组中,都有可能呈现屡次。

哈希表

在这里,咱们先说哈希表的思路。咱们能够应用哈希表来存储每个数字呈现的次数。在这里,咱们要求两个数组的交加,那么这里数字呈现的次数取决于两个数组中呈现次数较小的局部。

在这里,咱们能够思考对较短的数组进行遍历,在哈希表中记录数字以及对应呈现的次数。而后再遍历另外一个数组,如果数字存在于哈希表中,那么将数字增加到后果列表中,而后将哈希表对应数字的次数减 1。(这里抉择对较短数组进行遍历存哈希表,思考的是升高空间复杂度。)

对于哈希表思路的图解如下(示例 2):

具体实现代码见【代码实现 # 哈希表】

双指针

在题目前面的进阶当中第一个问题,提到如果数组都是曾经排好序的,该如何优化算法?

在这里,咱们能够思考应用双指针的办法。双指针思路的算法大抵如下:

  • 首先定义双指针,别离指向两个数组的首元素。
  • 开始比拟双指针指向的元素,对以下的状况进行解决:

    • 如果两个元素不相等,指针指向元素较小的向后挪动;
    • 如果两个元素相等,则将元素增加到后果列表中,而后两个指针同时向后挪动。
  • 当任意指针达到开端时,完结遍历。

对于双指针思路的图解如下(示例 2):

具体实现代码见【代码实现 # 双指针】

在这里,针对进阶的第三个问题大抵的阐明下。如果呈现 nums2 的元素存储在磁盘上,磁盘内存无限,无奈一次加载所有的元素到内存中。那么此时想要疾速进行排序,则不太可能,所以倡议应用哈希表的思路。针对哈希表的思路,数组波及的是查问操作,能够思考读取局部信息进行解决。

代码实现


# 哈希表
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 针对较短数组进行遍历将元素存于哈希表中
        # 保障后面的数组较短
        if len(nums1) > len(nums2):
            self.intersect(nums2, nums1)
        
        hash_map = {}

        for num in nums1:
            if num not in hash_map:
                hash_map[num] = 0
            hash_map[num] += 1
        
        ans = []

        for num in nums2:
            # 查看是否存在于哈希表中
            count = hash_map.get(num, 0)
            # 元素存在于哈希表中,则增加入后果列表中
            # 而后将哈希表对应的元素呈现次数减一
            if count > 0:
                ans.append(num)
                hash_map[num]-=1
        
        return ans

# 双指针
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()

        p = q = 0

        ans = []
        # 任意指针达到数组开端,完结遍历
        while p < len(nums1) and q < len(nums2):
            # 在这里,先判断指针对应元素的大小
            # 当不相等时,指针对应元素小的挪动
            # 相等时,将元素放入后果列表中,同时挪动指针
            if nums1[p] > nums2[q]:
                q+=1
            elif nums1[p] < nums2[q]:
                p += 1
            else:
                ans.append(nums1[p])
                p += 1
                q += 1
        
        return ans

实现后果


哈希表|实现后果

双指针|实现后果

欢送关注


公众号 【书所集录】

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据