Python求两个数组交集的排序双指针解法

本文分享一种使用Python计算两个数组交集的具体实现方案，供读者参考学习。

一、题目描述

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

示例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.sort()
nums2.sort()
result = []
i, j = 0, 0
while i<len(nums1) and j<len(nums2):
  if nums1[i]==nums2[j]:
    result.append(nums1[i])
    i += 1
    j += 1
  elif nums1[i]>nums2[j]:
    j += 1
  elif nums1[i]<nums2[j]:
    i += 1
return result

运行耗时52ms，性能优于93%的提交记录。

本地测试代码示例如下：

# -*- coding:utf-8 -*-
nums1 = [1,2,2,1]
nums2 = [2,2]
nums1.sort()
nums2.sort()
result = []
i, j = 0, 0
while i<len(nums1) and j<len(nums2):
  if nums1[i]==nums2[j]:
    result.append(nums1[i])
    i += 1
    j += 1
  elif nums1[i]>nums2[j]:
    j += 1
  elif nums1[i]<nums2[j]:
    i += 1
print(result)

执行输出结果：

[2, 2]

如需进一步了解Python相关知识，可参阅本站专题：《Python数组操作技巧总结》、《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》。

希望上述内容能对您的Python编程实践提供有益帮助。