LeetCode: (Python)(List) Find the Difference of Two Arrays

題目連結: https://leetcode.com/problems/find-the-difference-of-two-arrays/description/?envType=study-plan-v2&envId=leetcode-75

題意解析

• 給定兩個 lists，左邊 list只留和右邊 list不重複的數字，右邊 list只留和左邊 list不重複的數字
• 回傳數字不限制順序
• 回傳結果可能是完全空字串

解題思維

• 取 set搜尋才會快
• 找出一個大 set，包含左右兩邊不重複的數字
• 逐一檢查，如果數字同時在左右兩邊，remove

實作程式碼

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        set1 = set(nums1)
        set2 = set(nums2)
        merge_set = set1.union(set2)

        for n in merge_set:
            if n in set1 and n in set2:
                set1.remove(n)
                set2.remove(n)

        return [list(set1), list(set2)]

慘不忍睹的速度，但沒有 Timeout

解題思維二

• 重新理解題目
• 不需要找出包含左右兩邊不重複的數字，只要找出左右兩邊同時有的數字，也就是取交集
• 交集內的全部剔除

實作程式碼二

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        set1 = set(nums1)
        set2 = set(nums2)
        intersection = set1.intersection(set2)

        for n in intersection:
            set1.remove(n)
            set2.remove(n)

        return [list(set1), list(set2)]

解題思維三

• 詢問 ChatGPT
• 甚至不用找交集，直接將 set1排除 set2作為第一個回傳值，set2排除set1作為第二個回傳值

實作程式碼

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        set1, set2 = set(nums1), set(nums2)
        return [list(set1 - set2), list(set2 - set1)]

發現 Set的運算真的好用

• 聯集: set1 | set2
• 交集: set1 & set2
• 差集: set1 — set2
• 對稱差集: set1 ^ set2，取只在其中一個 set的
• 是否子集合: set1.issubset(set2), set1 <= set2
• 是否超集合: set1.issuperset(set2), set1 >= set2
• 是否完全無交集: set1.isdisjoint(set2)