LeetCode 筆記 - 349. Intersection of Two Arrays

題目在此 349. Intersection of Two Arrays

請找出兩個數列之間重複的元素

解題思維

由於題目要求答案必須是沒有重複的,所以我們可以先把數列先做成集合再開始做事

接下來再 Two Pointers 大法慢慢往下掃之前,記得需要先 Sorting

這個方法就可以在 O(N) 內把問題空間掃描一下

程式碼

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
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
if not nums1 or not nums2:
return []

nums1 = list(set(nums1))
nums2 = list(set(nums2))

size1 = len(nums1)
size2 = len(nums2)

nums1.sort()
nums2.sort()

index1 = index2 = 0

result = []
while index1 < size1 and index2 < size2:

if nums1[index1] < nums2[index2]:
index1 += 1
continue
elif nums1[index1] > nums2[index2]:
index2 += 1
continue

result.append(nums1[index1])

index1 += 1
index2 += 1

return result

也許你也會想看看