陣列與圖論綜合應用題 Find the Duplicate Number_Leetcode #287

閱讀時間約 4 分鐘
raw-image

這題的題目在這裡: 287. Find the Duplicate Number

題目會給我們一個輸入陣列,長度為n+1。

陣列裡面會有n+1個數字,數字的範圍從1到n

裡面恰好有一個數字重複出現,要求我們找出那個重複的數字

題目要求只能使用常數空間O(1),並且限制不能修改陣列內容。


測試範例:

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

約束條件:

Follow up:

  • How can we prove that at least one duplicate number must exist in nums?
  • Can you solve the problem in linear runtime complexity?

演算法:

除了使用傳統的雙層搜索之外,

還可以使用圖論中的Cycle detection演算法來尋找重複的數字

若我們把陣列每個位置想成一個節點

陣列內部的值,代表一條邊指向下一個節點的位置。

環路Cycle的起點,就對應到陣列中重複出現的數字

以範例一為例:

Input:
nums = [1,3,4,2,2]

raw-image

重複的數字是2

同時,二號節點,也是圖中環路Cycle的起點位置。


程式碼:

class Solution:
 def findDuplicate(self, nums: List[int]) -> int:
  
  # start hopping from Node_#0
  slow, fast = 0, 0

  # for locating start node of cycle
  check = 0
  
  # Step_#1
  # Cycle detection
  # Let slow jumper and fast jumper meet somewhere in the cycle

  while True:
   
    # slow jumper hops 1 step, while fast jumper hops two steps forward.
   slow = nums[ slow ]
   fast = nums[ nums[fast] ]
   
   if slow == fast:
    break
  

  # Step_#2
  # Locate the start node of cycle (i.e., the duplicate number)
  while True:
   
   slow = nums[ slow ]
   check = nums[ check ]
   
   if slow == check:
    break
  
  return check

複雜度分析

時間複雜度:

O(n) 整個陣列掃描至多兩遍

空間複雜度:

O(1) 耗費在slow, fast, check等臨時變數上,占用的記憶體空間皆固定O(1),
不會隨著問題規模放大而成長。


Reference:

[1] Python/JS/Java/Go/C++ O(1) aux space by hopping. [ w/ Hint ] — Find the Duplicate Number — LeetCode

avatar-img
89會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目會給定給我們一顆二元樹的根結點,要求我們輸出Level-order traversal的拜訪結果。 在這題,我們會複習並利用BFS模板,來實現逐層搜索演算法。
其實常見的tree traversal (前序、中序、後序拜訪), 背後的核心觀念都是相同的。 Tree traversal其實就是探索整顆樹的搜索空間,也可以說是探索整顆樹, 只是指定順序略有不同而已。 本文將結合經典的DFS模板,做一個全面性的回顧。
題目會給定一顆樹,要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。 我們會介紹DFS模板 + Tree search演算法的框架來解題
Leetcode #101 Symmetric Tree 題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
圖論常用的演算法BFS 與 DFS 的統整與比較。 介紹常用且相關的底層資料結構 並且,介紹幾個適合使用的應用領域、解題分類。
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
題目會給定給我們一顆二元樹的根結點,要求我們輸出Level-order traversal的拜訪結果。 在這題,我們會複習並利用BFS模板,來實現逐層搜索演算法。
其實常見的tree traversal (前序、中序、後序拜訪), 背後的核心觀念都是相同的。 Tree traversal其實就是探索整顆樹的搜索空間,也可以說是探索整顆樹, 只是指定順序略有不同而已。 本文將結合經典的DFS模板,做一個全面性的回顧。
題目會給定一顆樹,要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。 我們會介紹DFS模板 + Tree search演算法的框架來解題
Leetcode #101 Symmetric Tree 題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
圖論常用的演算法BFS 與 DFS 的統整與比較。 介紹常用且相關的底層資料結構 並且,介紹幾個適合使用的應用領域、解題分類。
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
你可能也想看
Google News 追蹤
Thumbnail
Hi 我是 VK~ 在 8 月底寫完〈探索 AI 時代的知識革命:NotebookLM 如何顛覆學習和創作流程?〉後,有機會在 INSIDE POSSIBE 分享兩次「和 NotebookLM 協作如何改變我學習和創作」的主題,剛好最近也有在許多地方聊到關於 NotebookLM 等 AI 工具
Thumbnail
國泰CUBE App 整合外幣換匯、基金、證券等服務,提供簡便、低成本的美股定期定額投資解決方案。 5分鐘開戶、低投資門檻,幫助新手輕鬆進軍國際股市;提供人氣排行榜,讓投資人能夠掌握市場趨勢。
Thumbnail
這是張老師的第三本書,我想前二本應該也有很多朋友們都有讀過,我想絕對是受益良多,而這次在書名上就直接點出,著重在從投資的角度來切入
Thumbnail
程式並不是寫完就可以自動運行,還需要經過「編譯」的階段。此篇文章會介紹編譯的四個階段,更貼近電腦科學。另外,也說明「陣列」的資料儲存模式跟實際的運用,提供優化程式的建議,最後再分享三個除錯的技巧。
Thumbnail
Array可以說是各種語言除了基本型別之外,最常用的資料型別與容器之一了。 Array 這種連續格子狀的資料結構,在Python要怎麼表達呢? 建立一個空的陣列 最簡單也最直接的寫法就是 array = [] # Python list [] 就對應到大家熟知的array 陣列型態的資料結
Thumbnail
今天是一堂原鄉體驗的課程,自己覺得幸福的是在美麗的校園唸書,又有機會深入更高海拔的山區學習。 我們的學習從鄒族的神聖場域開始一直到在自然中的教室 在信義國中校長 脈樹運用原鄉敘事帶領我們認識原民遷徙的歷史。 他也提到接下來的另一場遷徙是屬於心靈場域的遷徙(讓每個人都往內在沒有邊界的
Thumbnail
題目會給我們一個輸入陣列,長度為n+1。 陣列裡面會有n+1個數字,數字的範圍從1到n 裡面恰好有一個數字重複出現,要求我們找出那個重複的數字。 題目要求只能使用常數空間O(1),並且限制不能修改陣列內容。
Thumbnail
您是否苦於網路資訊爆炸嗎? 教學何其多,但卻無法好好選擇的困境呢? 歡迎加入「🔒 阿Han的軟體心法實戰營」, 這裡不給您冗餘的雜訊, 單刀直入直接送您重點, 避開選擇障礙的困境, 讓您獲得業界標準的開發起手式, 成為Top 1的頂尖人才。 我們是不是常常看到一些很厲害的專案, 只要「pip i
Thumbnail
👨‍💻簡介 在 Go 語言中,切片(Slice)是一種動態序列的資料結構,能夠方便地存儲和操作多個相同類型的元素。切片相比於陣列,更具有彈性,因為它的大小是可變的,可以根據需要動態增長或縮小。切片在處理集合型資料時非常實用,讓你能夠輕鬆地新增、刪除、修改和操作元素。
Thumbnail
👨‍💻簡介 陣列就像是一個儲存相同類型資料的容器,你可以想像成裝滿了一樣東西的盒子,每個東西都叫做陣列元素。這種類型可以是基本的,像是整數或字串,也可以是你自己定義的型別。不過陣列有個限制,就是大小一旦確定就無法改變。在Go語言裡,陣列的長度也是型別的一部分。
Thumbnail
你心目中的「家」是什麼樣子呢?我很喜歡《需要房子嗎?老鼠小姐來設計》最後海莉的生活樣貌,那是一處在針葉林裡,四周有著野菇、大樹圍繞,可以遠眺日出日落的平坦之地,她與夥伴正升火,準備煮食一頓美味的晚餐,他們的家僅僅是一個樸實簡單卻又溫暖的帳篷。
Thumbnail
Hi 我是 VK~ 在 8 月底寫完〈探索 AI 時代的知識革命:NotebookLM 如何顛覆學習和創作流程?〉後,有機會在 INSIDE POSSIBE 分享兩次「和 NotebookLM 協作如何改變我學習和創作」的主題,剛好最近也有在許多地方聊到關於 NotebookLM 等 AI 工具
Thumbnail
國泰CUBE App 整合外幣換匯、基金、證券等服務,提供簡便、低成本的美股定期定額投資解決方案。 5分鐘開戶、低投資門檻,幫助新手輕鬆進軍國際股市;提供人氣排行榜,讓投資人能夠掌握市場趨勢。
Thumbnail
這是張老師的第三本書,我想前二本應該也有很多朋友們都有讀過,我想絕對是受益良多,而這次在書名上就直接點出,著重在從投資的角度來切入
Thumbnail
程式並不是寫完就可以自動運行,還需要經過「編譯」的階段。此篇文章會介紹編譯的四個階段,更貼近電腦科學。另外,也說明「陣列」的資料儲存模式跟實際的運用,提供優化程式的建議,最後再分享三個除錯的技巧。
Thumbnail
Array可以說是各種語言除了基本型別之外,最常用的資料型別與容器之一了。 Array 這種連續格子狀的資料結構,在Python要怎麼表達呢? 建立一個空的陣列 最簡單也最直接的寫法就是 array = [] # Python list [] 就對應到大家熟知的array 陣列型態的資料結
Thumbnail
今天是一堂原鄉體驗的課程,自己覺得幸福的是在美麗的校園唸書,又有機會深入更高海拔的山區學習。 我們的學習從鄒族的神聖場域開始一直到在自然中的教室 在信義國中校長 脈樹運用原鄉敘事帶領我們認識原民遷徙的歷史。 他也提到接下來的另一場遷徙是屬於心靈場域的遷徙(讓每個人都往內在沒有邊界的
Thumbnail
題目會給我們一個輸入陣列,長度為n+1。 陣列裡面會有n+1個數字,數字的範圍從1到n 裡面恰好有一個數字重複出現,要求我們找出那個重複的數字。 題目要求只能使用常數空間O(1),並且限制不能修改陣列內容。
Thumbnail
您是否苦於網路資訊爆炸嗎? 教學何其多,但卻無法好好選擇的困境呢? 歡迎加入「🔒 阿Han的軟體心法實戰營」, 這裡不給您冗餘的雜訊, 單刀直入直接送您重點, 避開選擇障礙的困境, 讓您獲得業界標準的開發起手式, 成為Top 1的頂尖人才。 我們是不是常常看到一些很厲害的專案, 只要「pip i
Thumbnail
👨‍💻簡介 在 Go 語言中,切片(Slice)是一種動態序列的資料結構,能夠方便地存儲和操作多個相同類型的元素。切片相比於陣列,更具有彈性,因為它的大小是可變的,可以根據需要動態增長或縮小。切片在處理集合型資料時非常實用,讓你能夠輕鬆地新增、刪除、修改和操作元素。
Thumbnail
👨‍💻簡介 陣列就像是一個儲存相同類型資料的容器,你可以想像成裝滿了一樣東西的盒子,每個東西都叫做陣列元素。這種類型可以是基本的,像是整數或字串,也可以是你自己定義的型別。不過陣列有個限制,就是大小一旦確定就無法改變。在Go語言裡,陣列的長度也是型別的一部分。
Thumbnail
你心目中的「家」是什麼樣子呢?我很喜歡《需要房子嗎?老鼠小姐來設計》最後海莉的生活樣貌,那是一處在針葉林裡,四周有著野菇、大樹圍繞,可以遠眺日出日落的平坦之地,她與夥伴正升火,準備煮食一頓美味的晚餐,他們的家僅僅是一個樸實簡單卻又溫暖的帳篷。