349.两个数组的交集
题目描述
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
思路
- 集合求交集
- 排序+双指针
对nums1、nums2进行排序，设置两个指针index1、index2分别指向两个数组的头部，并按以下步骤进行：
（1）如果元素相等则加入结果列表
（2）如果index1指向的元素小于index2指向的元素，则index1指针后移，否则index2指针后移
不断执行以上两个步骤，最后结果列表中的元素即为两个数字的交集。代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51"""
集合操作
1.求交集
set1.intersection(set2)
2.求差集
set1.difference(set2)
3.求并集
set1.union(set2)
"""
class Solution(object):
def intersection(self, nums1, nums2):
"""
集合求交集
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
return list(set(nums1).intersection(set(nums2)))
def intersection1(self, nums1, nums2):
"""排序+双指针"""
nums1.sort()
nums2.sort()
index1 = 0
index2 = 0
intersection = list()
while index1 < len(nums1) and index2 < len(nums2):
if nums1[index1] == nums2[index2]:
if not intersection or nums1[index1] != intersection[-1]:
intersection.append(nums1[index1])
index1 += 1
index2 += 1
elif nums1[index1] < nums2[index2]:
index1 += 1
else:
index2 += 1
return intersection
if __name__ == "__main__":
slt = Solution()
nums1 = [2, 1]
nums2 = [1, 2]
# inter = slt.intersection(nums1, nums2)
inter = slt.intersection(nums1, nums2)
print(inter)