乐趣区

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

jiezi

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

实现后果

哈希表 | 实现后果

双指针 | 实现后果

欢送关注

公众号【书所集录】

退出移动版