陣列入門題 數有幾個好配對 Number of Good Pairs_Leetcode #1512

這題的題目在這裡:

題目敘述

題目會給定我們一個輸入陣列，要求我們計算好配對的數目有多少個?

好配對的定義: 兩個數字相同，但是陣列索引一個在前，一個在後。
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