題目出處

350. Intersection of Two Arrays II

難度

Easy

題目分類

hash-table, two-pointers, binary-search, sort

個人範例程式碼 – 2022/5/12 三刷

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        intersect_counter = (Counter(nums1) & Counter(nums2))

        ans = []
        for key, value in intersect_counter.items():
            for _ in range(value):
                ans.append(key)

        return ans

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

• 此題目的前一題為不需要進行重複處理，這題需要處理重複，可參考：

【Leetcode】python – [349] Intersection of Two Arrays 個人解法筆記

Counter & Counter：可以找到所有重複的數值 & 數量

這裡特別注意：很幸運的，他有幫我們處理掉 「”3個重複數” & “2個重複數” = “2個重複數”」 的情況，
不然我們預期可能直接因為數量不同就 False，這樣我們就不能使用這個方法了。

input handling

dict and 的過程中會處理掉

Boundary conditions

x

個人範例程式碼 – 2022/3/4 二刷 (set & counter 流)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        for ele in (set(nums1) & set(nums2)):
            for i in range(min(Counter(nums1)[ele], Counter(nums2)[ele])):
                ans.append(ele)
        return ans

說明

這題看到求「重複」的，第一個直覺反應是不是會想到用 set 呢?
可是一用 set 之後，就會發現這題目設計的難度之處，
不過沒關係，遇到重複了，我們還有 Counter!

先用 set 快速找出有重複的，
再用確定有重複的，計算數量後，取較少的即可得到答案。

corner case 特殊情況處理

記得要找的是兩個集合的 min，而不是「只找單邊」

Boundary conditions/ Edge conditions 邊際情況處理

x

個人範例程式碼 – 2022/2/25 一刷 (two pointer 流)

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        # print(set(nums1) & set(nums2))
        nums1, nums2 = sorted(nums1), sorted(nums2)
        res = []
        pt1, pt2 = 0, 0
        while(pt1 < len(nums1) and pt2 < len(nums2)):
            if nums1[pt1] > nums2[pt2]:
                pt2 += 1
            elif nums1[pt1] < nums2[pt2]:
                pt1 += 1
            else: # nums1[pt1] == nums2[pt2]
                res.append(nums1[pt1])
                pt1 += 1
                pt2 += 1
        return res

說明

這題看到求「重複」的，第一個直覺反應是不是會想到用 set 呢?
可是一用 set 之後，就會發現這題目設計的難度之處，
因為它是允許有 [1,1,2,2] 去交集 [2,2] 的
所以如果我門直接用 set，會把重複的 2 給用掉。
因此這題不能用 set 的作法。

我們採用的是 sort 後並使用兩個 pointer，一個個對照，
只要發現比較小的那側，就往下一個數字前進，
而如果兩者是一樣的，我們就同時一起前進。

邊際情況處理

這題目需要處理的邊際情況為 pointer 什麼時候結束，
我們需要知道，當其中一個 pointer 已經「指完了全部的內容」，
就沒有繼續往下看的必要了。因為另外一個再往下看，也一定找不到一樣的值。

所以我們使用 while 設定範圍在 pt1 < len(nums1) 的範圍內，
就可以處理這個問題。

Reference

• 两数组的交集 II · Intersection of Two Arrays II
• Three Python Solutions