這題的題目在這裡: 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]
重複的數字是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
