題目出處
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,可以嘗試直接閱讀程式碼理解
算法說明
- 此題目的前一題為不需要進行重複處理,這題需要處理重複,可參考:
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 Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|