題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個?
好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。nums[i] == nums[j]
and i
< j
.
這樣 (i, j) 就稱為一組好配對。
Example 1:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Example 2:
Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.
Example 3:
Input: nums = [1,2,3]
Output: 0
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100
除了第一直覺,雙層迴圈直接去模擬good pair的生成並且計數以外;這題還有一個高效率的排列組合作法。
對任何一個給定數字num,假如出現k次,那與num有關的good pair數目其實就等於C(k, 2) = C k 取 2 = k * (k-1) / 2
因為任選兩個不同位置的num,都構成一個good pair
所以,只要先做一個字典,統計每個數字的出現次數。
接著,針對每個數字,由C(k, 2)的組合公式計算good pair數目,並且加總,就是最後答案。
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
occurrence = Counter( nums )
pair = 0
for num, occ in occurrence.items():
pair += occ * (occ-1) // 2
return pair
時間複雜度:
O( n ) 建造字典掃描數字耗費O(n),掃描字典內的數字也耗費O(n)。
空間複雜度:
O( n ) 字典大小最大和陣列一樣長,所佔用空間為O(n)。
觀察並且模擬幾個小範例,可以發現good pair背後的原理其實就是n個物品,任選兩個的方法數,可以由排列組合公式計算得到答案。
Reference:
[1] Python sol by iteration - Number of Good Pairs - LeetCode