→ yam276: 我的想法是從頭往尾跑 只要碰到可以成隊的 前面有幾個就加 10/03 23:52
→ yam276: 幾次 這樣順著跑還不用考慮排列啥的 10/03 23:52
推 wu10200512: 你是誰 10/04 00:50
我的想法比較不一樣，偏數學一點：
由題目可以得知出現次數在兩次以下的不構成 Pair，
而兩次以上的情形，我們可以用排列組合中的組合去計算。
當某數出現 N 次時，其可能組成的 Pair 數為 C(N, 2)。
你可能會問說：可是這題有順序之分啊？怎麼不是用排列呢？
沒有錯，確實要考慮順序，
但其實在這題裡，當你在從 N 個出現位子中取 2 位出來時，也順便幫他們排列好了，意即：
取出 i 與 j，其中 i 與 j 分別代表出現的位子
那他們的排列要嘛是 i, j，要嘛是 j, i
而我們只需要其中一種，所以其實就是組合
Code:
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
c = Counter(nums)
result = 0
for times in c.values():
if times >= 2:
result += math.comb(times, 2)
return result
Note:
其實可以利用 math.comb 的特性 (math.comb(k, n) = 0 for n > k) 去省略掉判斷 times 是不是大於 2
然後其實可以塞成一行 XD
return sum(math.comb(times, 2) for times in collections.Counter(nums).values())
※ 引述《yam276 (史萊哲林的優等生)》之銘言：
: ※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: : 1512. Number of Good Pairs
: : 給你一個整數陣列 nums，如果 nums[i] == nums[j] 且 i < j 則 (i, j) 是一個
: : Pair，求出 nums 共有幾個 Pair。
: : 思路：
: : 1.用一個 map 記錄之前出現過的數字數量，因為 nums[i] 介於 0 到 100 所以用
: : int[101]。
: : 2.每一輪可以產生的 Pair 為累計先前出現過的數量，把每一輪的結果加總即可。
: 思路：
: 跟這個差不多
: 主要是每次出現新數字就會多N個組合所以邏輯是result+=count;
: count+=1;
: 以及學到快速使用HashMap：
: *nums_map.entry(num).or_insert(0) += 1;
: .entry(num) : 尋找key(num)-value是存在
: .or_insert(0) ： key(num)-value存在
: 就會給你value的可變引用並進行後面操作(+=1)
: key(num)-value不存在
: 則會用初始值(0)建立一對key(num)-value
: 並給你value的可變引用
: 再用這個可變引用做後面操作(+=1)
: Code:
: use std::collections::HashMap;
: impl Solution {
: pub fn num_identical_pairs(nums: Vec<i32>) -> i32 {
: let mut nums_map = HashMap::new();
: let mut result = 0;
: for num in &nums {
: match nums_map.get(num) {
: Some(count) => {
: result += count;
: }
: None => {}
: }
: *nums_map.entry(num).or_insert(0) += 1;
: }
: result
: }
: }
--
僕の妹がこんなに可愛いわけがない担当のアユニ‧D です
https://i.imgur.com/Zvo15mG.jpg
https://twitter.com/AYUNiD_BiSH
https://instagram.com/ayunid_official
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.240.222.158 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1696348044.A.2B8.html