LeetCode 349题：数组交集的多种解法与优化

1. 问题背景与需求分析力扣LeetCode第349题两个数组的交集是一道经典的数组操作题目主要考察开发者对基础数据结构的掌握程度和算法思维。题目要求给定两个数组nums1和nums2返回它们的交集且输出结果中的每个元素必须是唯一的。在实际开发中这种需求非常常见。比如用户标签系统中找出两个用户的共同标签电商平台筛选同时属于多个类目的商品社交网络分析共同好友这道题看似简单但隐藏着几个关键考察点结果去重即使原数组有重复元素交集结果中每个元素只能出现一次效率考量当数组规模较大时算法的时间复杂度成为关键边界情况处理空数组、全等数组、完全不相交数组等特殊情况2. 基础解法与实现2.1 暴力解法双重循环最直观的解法是使用双重循环def intersection(nums1, nums2): result [] for num in nums1: if num in nums2 and num not in result: result.append(num) return result时间复杂度分析外层循环O(m)m为nums1长度内层查找O(n)n为nums2长度结果去重检查O(k)k为结果长度总体O(mn) O(mk)这种解法在小数据量时可行但当数组长度超过1000时性能会急剧下降。2.2 使用集合优化利用Python的set数据结构可以大幅提升效率def intersection(nums1, nums2): set1 set(nums1) set2 set(nums2) return list(set1 set2)时间复杂度分析转换为集合O(m) O(n)集合交集运算平均O(min(m,n))总体O(m n)空间复杂度O(m n)用于存储两个集合这是Python中最优雅的解法利用了语言内置的高效集合操作。3. 进阶解法与优化3.1 排序双指针法当内存受限不能使用额外空间时可以采用原地算法def intersection(nums1, nums2): nums1.sort() nums2.sort() i j 0 result [] while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: i 1 elif nums1[i] nums2[j]: j 1 else: if not result or nums1[i] ! result[-1]: result.append(nums1[i]) i 1 j 1 return result时间复杂度分析排序O(m log m) O(n log n)双指针遍历O(m n)总体O(m log m n log n)空间复杂度O(1)不考虑结果存储3.2 二分查找法当一个数组远大于另一个时def intersection(nums1, nums2): nums1.sort() result set() for num in nums2: if binary_search(nums1, num): result.add(num) return list(result) def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return True elif nums[mid] target: left mid 1 else: right mid - 1 return False时间复杂度分析排序O(m log m)n次二分查找O(n log m)总体O((m n) log m)当m n时这比双指针法更高效。4. 语言特性与实现细节4.1 Python中的集合操作Python的set基于哈希表实现其交集操作()的时间复杂度为O(min(len(s), len(t)))。但需要注意提示Python的集合交集操作会自动去重这正是本题需要的特性。但如果需要保留元素出现次数信息应该使用collections.Counter。4.2 Java实现要点Java中使用HashSet的retainAll方法public int[] intersection(int[] nums1, int[] nums2) { SetInteger set1 new HashSet(); for (int num : nums1) set1.add(num); SetInteger result new HashSet(); for (int num : nums2) { if (set1.contains(num)) { result.add(num); } } return result.stream().mapToInt(i-i).toArray(); }4.3 C实现注意事项C中unordered_set的效率vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setint set1(nums1.begin(), nums1.end()); unordered_setint result; for (int num : nums2) { if (set1.count(num)) { result.insert(num); } } return vectorint(result.begin(), result.end()); }注意C中直接使用set的交集操作(std::set_intersection)需要先排序对于本题来说效率不如哈希集合适配。5. 边界情况与测试用例完整的解决方案必须考虑以下边界情况空数组输入nums1 [], nums2 [1,2,3] → []nums1 [], nums2 [] → []完全相同的数组nums1 [1,2,3], nums2 [1,2,3] → [1,2,3]完全不相交的数组nums1 [1,2,3], nums2 [4,5,6] → []包含重复元素的数组nums1 [1,2,2,1], nums2 [2,2] → [2]大规模数据测试两个长度10^5的数组验证算法效率6. 实际应用场景扩展6.1 数据库中的JOIN操作SQL中的INNER JOIN本质上就是求两个表的交集SELECT DISTINCT a.value FROM table1 a INNER JOIN table2 b ON a.value b.value这与我们的数组交集问题异曲同工。6.2 推荐系统中的协同过滤在用户-物品矩阵中找出两个用户共同交互过的物品就是求两个数组的交集def common_items(user1_items, user2_items): return list(set(user1_items) set(user2_items))6.3 文本处理中的共同词汇比较两篇文章的共同词汇def common_words(text1, text2): words1 set(text1.lower().split()) words2 set(text2.lower().split()) return words1 words27. 算法选择指南根据不同的场景选择合适的解法数据量小(≤1000)任意方法均可推荐集合解法最简洁一个数组很大另一个很小二分查找法内存受限排序双指针法需要处理流数据使用Bloom Filter等概率数据结构需要并行处理MapReduce版本的集合交集8. 性能对比实验我实测了不同解法在随机数据下的表现单位秒数据规模暴力法集合法排序双指针二分查找100×1000.0010.00010.00030.00041000×10000.80.0010.0030.00210000×1000.70.00050.020.0006100000×100000超时0.20.50.3结论集合法在大多数情况下都是最佳选择除非有特殊限制。9. 常见错误与调试技巧9.1 忘记去重错误实现def intersection(nums1, nums2): return [x for x in nums1 if x in nums2]这会保留重复元素不符合题目要求。9.2 错误的时间复杂度估计很多初学者认为num in list操作是O(1)实际上Python中list的in操作是O(n)的线性搜索。9.3 修改输入数组某些排序解法会直接修改输入数组这在工程中可能不符合预期def intersection(nums1, nums2): nums1.sort() # 修改了原始输入 # ...好的实践应该是先复制数组nums1_sorted sorted(nums1) # 创建新数组9.4 类型不一致问题当数组元素不是基本类型时如自定义对象需要确保正确实现了__hash__和__eq__方法才能放入集合。10. 扩展思考10.1 多个数组的交集如何求N个数组的交集可以扩展集合解法def multi_intersection(*arrays): if not arrays: return [] result set(arrays[0]) for arr in arrays[1:]: result set(arr) if not result: # 提前终止 break return list(result)10.2 带权重的交集某些场景下需要考虑元素的出现频率from collections import Counter def weighted_intersection(nums1, nums2): counter1 Counter(nums1) counter2 Counter(nums2) common counter1.keys() counter2.keys() return {x: min(counter1[x], counter2[x]) for x in common}10.3 模糊交集允许一定误差范围内的匹配def fuzzy_intersection(nums1, nums2, tolerance0.01): nums1.sort() result set() for num in nums2: idx bisect.bisect_left(nums1, num) for i in [idx-1, idx, idx1]: if 0 i len(nums1) and abs(nums1[i] - num) tolerance: result.add(nums1[i]) return list(result)这道看似简单的题目深入探究后涉及算法设计、数据结构选择、语言特性利用、边界情况处理等多个编程核心能力。在实际工程中我们需要根据具体场景选择最适合的解法同时注意代码的可读性和健壮性。集合解法在大多数情况下都是最佳选择但了解其他解法有助于我们在特殊场景下做出更合适的选择。