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

閱讀時間約 2 分鐘
raw-image

這題的題目在這裡:

題目敘述

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

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

avatar-img
88會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目會給定我們一個陣列和參數k,要求我們將陣列右旋k次,然後輸出內容。 例如[1,2,3,4,5] 右旋 2次,輸出就是[4,5,1,2,3]
題目會給定我們一個陣列,要求我們找出裡面統計最多出現次數的偶數 。 假如有兩個偶數出現的次數一樣多,取最數字比較小的那個最為答案。
題目會給定我們一個陣列,陣列長度為n。 要求我們找出裡面出現次數超過 n / 3次的數字。
題目會給定我們一個輸入陣列,裡面的字母A和字母B分別代表兩種顏色的卡片。 假如某張卡片的左右都是相同的,例如AAA,Alice可以抽掉中間那張A。 同樣的,假如某張卡片的左右都是相同的,例如BBB,Bob可以抽掉中間那張B。 請問Alice和Bob輪流玩抽卡遊戲, 請問最後是誰贏?
題目給定一個已排序的輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目給定一個輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目會給定我們一個陣列和參數k,要求我們將陣列右旋k次,然後輸出內容。 例如[1,2,3,4,5] 右旋 2次,輸出就是[4,5,1,2,3]
題目會給定我們一個陣列,要求我們找出裡面統計最多出現次數的偶數 。 假如有兩個偶數出現的次數一樣多,取最數字比較小的那個最為答案。
題目會給定我們一個陣列,陣列長度為n。 要求我們找出裡面出現次數超過 n / 3次的數字。
題目會給定我們一個輸入陣列,裡面的字母A和字母B分別代表兩種顏色的卡片。 假如某張卡片的左右都是相同的,例如AAA,Alice可以抽掉中間那張A。 同樣的,假如某張卡片的左右都是相同的,例如BBB,Bob可以抽掉中間那張B。 請問Alice和Bob輪流玩抽卡遊戲, 請問最後是誰贏?
題目給定一個已排序的輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目給定一個輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
你可能也想看
Google News 追蹤
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
財政部北區國稅局表示,營利事業出售國內上市(櫃)、未上市(櫃)股票之所得,依所得稅法第4條之1規定,屬證券交易所得停止課徵所得稅,惟依所得基本稅額條例第7條第1項規定,計算基本所得額時應加計前揭所得。另依同條例第7條第2項規定,經稽徵機關核定之證券交易損失,得自發生年度之次年度起5年內,從當年度之證
不管在星星兒進行適應轉變的過程而引導,甚至在星星兒得不到具體明確的回應,要是因此霸凌星星兒,務必列入永無止盡的黑名單。 防止星星兒的二次傷害 在星星兒的立場,因為知人知面不知心,導致星星兒無法判斷人心的善惡。 畢竟,人很複雜。 當然,真要說,有星星兒在適應轉變,而無法適應轉變,反而出現嚴重傷
摘要 當公司出售證券有獲利時,需要申報基本所得額,也就是記入最低稅負制 正文 財政部北區國稅局表示,營利事業出售國內上市(櫃)、未上市(櫃)股票之所得,依所得稅法第4條之1規定,屬證券交易所得停止課徵所得稅,惟依所得基本稅額條例第7條第1項規定,計算基本所得額時應加計前揭所得。另依同條
Thumbnail
前9個月,流入越南房地產的外資佔FDI近10% 今年前9月,流入越南房地產的外國直接投資資金(FDI)達19.4億美元,佔FDI的9.6%。 從吸收外資情況來看,外國投資者對21個國民經濟產業中的18個產業進行投資。其中,加工製造業仍領先,投資總額超140億美元,佔註冊投資總額的近69.3%,較
Thumbnail
題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個? 好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。 nums[i] == nums[j] and i < j. 這樣 (i, j) 就稱為一組好配對。
Thumbnail
👨‍💻簡介 陣列就像是一個儲存相同類型資料的容器,你可以想像成裝滿了一樣東西的盒子,每個東西都叫做陣列元素。這種類型可以是基本的,像是整數或字串,也可以是你自己定義的型別。不過陣列有個限制,就是大小一旦確定就無法改變。在Go語言裡,陣列的長度也是型別的一部分。
Thumbnail
我們人生中所有吸引來的人、事、物都跟我們的振動頻率息息相關,如果我們可以在我們人生中遇到各種決擇的時候,有更好的選項可以做為方案,提高振動頻率就是宇宙送給我們最棒的禮物。因為,只要我們不斷的提升振動,更多更好更棒的選擇,便是由我們自己創造了。
Thumbnail
這幾天FB一直推播振光大直熄燈跳樓大特價的廣告給我,我檢舉一個又來一個。原本這種東西我用膝蓋想都知道100%是詐騙,就算有收到東西也不會是正版的模型。
Thumbnail
莫瑞泰斯皇家美術館積極邀請大家「交出你的珍珠耳環少女!」,提供自己受到《戴著珍珠耳環的少女》啟發的作品,任何形式、任何媒材,通通都可以!
Thumbnail
隨著奧斯卡的落幕, 這一巴掌響出天際成為熱門題材, 成為大家爭相討論模仿的話題, 但其實這背後也帶出許多的議題討論 2022年第94屆奧斯卡頒獎典禮上,喜劇演員—克里斯洛克(Chris Rock) 在舞台上大開威爾史密斯(Will Smith)的妻子 便衝上台給了克里斯一個響亮的巴掌,
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
財政部北區國稅局表示,營利事業出售國內上市(櫃)、未上市(櫃)股票之所得,依所得稅法第4條之1規定,屬證券交易所得停止課徵所得稅,惟依所得基本稅額條例第7條第1項規定,計算基本所得額時應加計前揭所得。另依同條例第7條第2項規定,經稽徵機關核定之證券交易損失,得自發生年度之次年度起5年內,從當年度之證
不管在星星兒進行適應轉變的過程而引導,甚至在星星兒得不到具體明確的回應,要是因此霸凌星星兒,務必列入永無止盡的黑名單。 防止星星兒的二次傷害 在星星兒的立場,因為知人知面不知心,導致星星兒無法判斷人心的善惡。 畢竟,人很複雜。 當然,真要說,有星星兒在適應轉變,而無法適應轉變,反而出現嚴重傷
摘要 當公司出售證券有獲利時,需要申報基本所得額,也就是記入最低稅負制 正文 財政部北區國稅局表示,營利事業出售國內上市(櫃)、未上市(櫃)股票之所得,依所得稅法第4條之1規定,屬證券交易所得停止課徵所得稅,惟依所得基本稅額條例第7條第1項規定,計算基本所得額時應加計前揭所得。另依同條
Thumbnail
前9個月,流入越南房地產的外資佔FDI近10% 今年前9月,流入越南房地產的外國直接投資資金(FDI)達19.4億美元,佔FDI的9.6%。 從吸收外資情況來看,外國投資者對21個國民經濟產業中的18個產業進行投資。其中,加工製造業仍領先,投資總額超140億美元,佔註冊投資總額的近69.3%,較
Thumbnail
題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個? 好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。 nums[i] == nums[j] and i < j. 這樣 (i, j) 就稱為一組好配對。
Thumbnail
👨‍💻簡介 陣列就像是一個儲存相同類型資料的容器,你可以想像成裝滿了一樣東西的盒子,每個東西都叫做陣列元素。這種類型可以是基本的,像是整數或字串,也可以是你自己定義的型別。不過陣列有個限制,就是大小一旦確定就無法改變。在Go語言裡,陣列的長度也是型別的一部分。
Thumbnail
我們人生中所有吸引來的人、事、物都跟我們的振動頻率息息相關,如果我們可以在我們人生中遇到各種決擇的時候,有更好的選項可以做為方案,提高振動頻率就是宇宙送給我們最棒的禮物。因為,只要我們不斷的提升振動,更多更好更棒的選擇,便是由我們自己創造了。
Thumbnail
這幾天FB一直推播振光大直熄燈跳樓大特價的廣告給我,我檢舉一個又來一個。原本這種東西我用膝蓋想都知道100%是詐騙,就算有收到東西也不會是正版的模型。
Thumbnail
莫瑞泰斯皇家美術館積極邀請大家「交出你的珍珠耳環少女!」,提供自己受到《戴著珍珠耳環的少女》啟發的作品,任何形式、任何媒材,通通都可以!
Thumbnail
隨著奧斯卡的落幕, 這一巴掌響出天際成為熱門題材, 成為大家爭相討論模仿的話題, 但其實這背後也帶出許多的議題討論 2022年第94屆奧斯卡頒獎典禮上,喜劇演員—克里斯洛克(Chris Rock) 在舞台上大開威爾史密斯(Will Smith)的妻子 便衝上台給了克里斯一個響亮的巴掌,