字典應用:兩個陣列的交集II_Intersection of Two Arrays II_Leetcode #350

Vera De on Unsplash

題目敘述 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)。

Reference

[1] Intersection of Two Arrays II - LeetCode