前往
大廳
主題

LeetCode - 1512. Number of Good Pairs 解題心得

Not In My Back Yard | 2023-02-11 12:00:01 | 巴幣 1000 | 人氣 208

題目連結:


題目意譯:
給定一整數陣列 nums,回傳好數對的數量。

一個數對 (i, j) 如果滿足 nums[i] == nums[j] 且 i < j,則其將被稱為好數對。

限制:
1 ≦ nums.length ≦ 100
1 ≦ nums[i] ≦ 100



範例測資:
範例 1:
輸入: nums = [1,2,3,1,1,3]
輸出: 4
解釋: 有 4 個 (0, 3) 、 (0, 4) 、 (3, 4) 、 (2, 5)(索引值從 0 開始)。

範例 2:
輸入: nums = [1,1,1,1]
輸出: 6
解釋: 陣列中每一個數對都是好數對。

範例 3:
輸入: nums = [1,2,3]
輸出: 0


解題思維:
先把 nums 由小排到大(索引值 i < j 這個條件沒有這麼重要,重要的是數值本身),因此相同數值的數字會排在一起(不過因為這題的數值範圍很小,所以也可以直接開陣列來統計)。接著就掃過一次來統計每一種數字的出現次數。

假設現在有一種數字出現了 C 次,則該種數字會有 C × (C - 1) ÷ 2 個好數對存在於其中。

將每一種數字貢獻的好數對加總即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作