題目敘述 Intersection of Two Arrays II
給定兩個輸入陣列，請找出兩個陣列交集的元素，並且依照出現次數輸出。
測試範例
Example 1:Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
交集元素:2
對應的出現次數[2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.
交集元素:4,9
對應的出現次數[4,9]
約束條件
Constraints:
1 <= nums1.length, nums2.length <= 1000
陣列長度介於1~1000之間。
0 <= nums1[i], nums2[i] <= 1000
每個陣列元素介於0~1000之間。
觀察 交集 與 出現次數
交集就是兩個集合重疊的元素。
接著，可以用字典來記錄每個元素的出現次數。
演算法 用字典來記錄出現次數
先針對兩個輸入陣列建立對應的字典。
接著取交集，接著依照出現次數輸出對應的交集元素。
程式碼 用字典來記錄出現次數
from collections import Counter
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
# build number-occurence dictionary for nums1 and nums2
num_occ_dict_1, num_occ_dict_2 = map( Counter, [ nums1, nums2 ] )
# compute intersection
intersection = num_occ_dict_1 & num_occ_dict_2
# output intersection element with corresponding occurrences
return sum( ( [num]*occ for num, occ in intersection.items() ), [] )
複雜度分析
時間複雜度: O(m+n)
兩個陣列依序建立字典，所需時間為O(m)+O(n) = O(m+n)。
空間複雜度: O(m+n)
兩個陣列依序建立字典，所需空間亦為O(m)+O(n) = O(m+n)。
