企业官网建设流程全解析

LeetCode 两个数组的交集题解

题目描述

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

示例：

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

解题思路

方法：哈希表

思路：

• 使用哈希表来解决这个问题。
• 首先遍历第一个数组，将每个元素存入哈希表中。
• 然后遍历第二个数组，对于每个元素，如果在哈希表中存在，将其加入结果列表，并从哈希表中移除该元素。
• 最后返回结果列表。

复杂度分析：

• 时间复杂度：O(m + n)，其中 m 和 n 分别是两个数组的长度。
• 空间复杂度：O(min(m, n))，需要额外的空间来存储哈希表。

代码实现

方法：哈希表

from collections import defaultdict # 两个数组的交集（哈希表） def intersection(nums1, nums2): # 创建哈希表，统计 nums1 中每个元素出现的次数 count = defaultdict(int) for num in nums1: count[num] += 1 # 遍历 nums2，找出交集元素 result = [] seen = set() for num in nums2: if count[num] > 0 and num not in seen: result.append(num) seen.add(num) return result # 测试 def test_intersection(): nums1 = [1, 2, 2, 1] nums2 = [2, 2] print(intersection(nums1, nums2)) # 输出：[2] nums1 = [4, 9, 5] nums2 = [9, 4, 9, 8, 4] print(intersection(nums1, nums2)) # 输出：[9, 4] if __name__ == "__main__": test_intersection()

方法：集合

# 两个数组的交集（集合） def intersection_set(nums1, nums2): set1 = set(nums1) set2 = set(nums2) return list(set1 & set2) # 测试 def test_intersection_set(): nums1 = [1, 2, 2, 1] nums2 = [2, 2] print(intersection_set(nums1, nums2)) # 输出：[2] if __name__ == "__main__": test_intersection_set()

测试用例

测试用例 1：基本情况

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

测试用例 2：多个交集元素

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

总结

两个数组的交集是一个经典的哈希表问题，它可以通过哈希表或集合来高效地解决。

哈希表法的核心思想是：使用哈希表统计第一个数组中每个元素出现的次数，然后遍历第二个数组，找出在哈希表中存在的元素。

集合法的核心思想是：将两个数组转换为集合，然后求交集。

掌握哈希表和集合的使用方法，对于解决类似的问题非常重要。