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

這題的題目在這裡:

題目會給我們一個輸入陣列，長度為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]

重複的數字是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