LeetCode 筆記 - 349. Intersection of Two Arrays

Posted on 標籤
找出兩個數列中重複的元素，且結果不包含重複值。本文介紹先將數列轉換為集合（set）以去除冗餘，再透過排序後利用雙指針（Two Pointers）進行同步掃描的策略。這種方法能確保在 O(N) 時間內精確找出交集元素。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 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

也許你也會想看看