項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [350] Intersection of Two Arrays II 個人解法筆記 (updated: 2022/5/12)

題目出處

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

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote