当前位置：首页 > news >正文

【Python3】【力扣题】349. 两个数组的交集

news 来源：原创 2024/5/12 9:58:59

【力扣题】题目描述：

【Python3】代码：

1、解题思路：集合的交集。两个数组都转为集合，获取集合的交集。

知识点：set(...)：转为集合，集合的元素不重复。

集合1.intersection(集合2)：获取两个集合都有的元素，即两集合的交集。也可以：集合1 & 集合2。

list(...)：转为列表。

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:res = set(nums1) & set(nums2)return list(res)# 或者res = set(nums1).intersection(set(nums2))return list(res)

2、解题思路：遍历数组，依次判断元素是否在另一个数组中，用新列表记录两个数组都有的元素。

知识点：集合推导式：用简洁的方法创建集合，集合中的元素不能重复。{ 对元素的简单操作 for 变量 in 可迭代对象 if 条件 }。

列表推导式：用简洁的方法创建列表，列表中的元素可以重复。[ 对元素的简单操作 for 变量 in 可迭代对象 if 条件 ]。

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:aset = set(nums1)res = {x for x in nums2 if x in aset}return list(res)# 或者aset, bset = set(nums1), set(nums2)return [x for x in bset if x in aset]

也可遍历长度短的数组，以提升一点速度。

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:aset = set(nums1)bset = set(nums2)return self.set_intersection(aset,bset)def set_intersection(self,set1,set2):if len(set1) > len(set2):return self.set_intersection(set2,set1)return [x for x in set1 if x in set2]

注解：集合推导式、列表推导式

# 集合推导式
res = {x for x in nums2 if x in aset}
# 相当于：
res = set()
for x in nums2:if x in aset:res.append(x)
print(res)# 列表推导式
res = [x for x in bset if x in aset]
# 相当于：
res = []
for x in bset:if x in aset:res.append(x)
print(res)

3、解题思路：排序+双指针。将两数组都排序，依次比较两数组中的元素大小。若相同，则用新列表记录；若不同，则较小数字的指针往后移，继续比较，直到两数组所有元素比较结束。

知识点：列表.sort()：在原列表基础上，将元素按从小到大排序。

len(列表)：获取列表长度，即列表中有多少元素。

列表.append(...)：往列表尾部添加元素。

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:res = []nums1.sort()nums2.sort()len_1, len_2 = len(nums1), len(nums2)index_1, index_2 = 0, 0while index_1 < len_1 and index_2 < len_2 :val_1 = nums1[index_1]val_2 = nums2[index_2]if val_1 == val_2 and val_1 not in res:res.append(val_1)index_1 += 1index_2 += 1elif val_1 < val_2:index_1 += 1else:index_2 += 1return res