Description
給定一個包含
n + 1個整數的陣列nums，其中每個整數都在[1, n]範圍內。保證至少存在一個重複數字。在不修改陣列且只使用 O(1) 額外空間的條件下，找出重複的數字。
Example:
Input: nums = [1,3,4,2,2] Output: 2
Intuition#
核心思路：把陣列看成隱式鏈結串列（index -> nums[index]），重複數字意味著有環，環的入口就是答案。
- nums 中的值範圍是 [1, n]，可以作為索引使用
- 從 index 0 開始，下一個位置是 nums[0]，再下一個是 nums[nums[0]]…
- 重複數字會導致兩個不同索引指向同一位置，形成環
- 環的入口就是重複的數字，用 Floyd’s Algorithm 找到
Approaches#
1: Binary Search on Value Range#
- 概念: 對值域 [1, n] 做二分搜尋。對於中間值 mid，計算陣列中 <= mid 的元素個數。如果個數 > mid，則重複數字在 [1, mid] 中
- 時間複雜度:
O(n log n)- 二分搜尋 log n 次，每次計數 O(n) - 空間複雜度:
O(1)
class Solution {
fun findDuplicate(nums: IntArray): Int {
var low = 1
var high = nums.size - 1
while (low < high) {
val mid = low + (high - low) / 2
val count = nums.count { it <= mid }
if (count > mid) {
high = mid
} else {
low = mid + 1
}
}
return low
}
}⭐2: Floyd’s Cycle Detection#
- 概念: 將陣列視為隱式鏈結串列，用快慢指針找到環的入口（即重複數字）
- 時間複雜度:
O(n)- 快慢指針各遍歷有限次 - 空間複雜度:
O(1)- 只用兩個指針
class Solution {
fun findDuplicate(nums: IntArray): Int {
// Phase 1: 找到相遇點
var slow = nums[0]
var fast = nums[0]
do {
slow = nums[slow]
fast = nums[nums[fast]]
} while (slow != fast)
// Phase 2: 找到環的入口
slow = nums[0]
while (slow != fast) {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
}Phase 2 的數學原理：設起點到環入口距離為 a，環入口到相遇點距離為 b，環長為 c。相遇時 slow 走了 a+b，fast 走了 a+b+c。因為 fast 速度是 slow 的兩倍：2(a+b) = a+b+c，所以 a = c-b。因此從起點和相遇點各走 a 步後必在入口相遇。
補充：Bit Manipulation 解法
對於每個 bit 位，分別計算 [1,n] 中該位為 1 的個數和 nums 中該位為 1 的個數。如果 nums 中更多，說明重複數字在該位為 1。
class Solution {
fun findDuplicate(nums: IntArray): Int {
val n = nums.size - 1
var result = 0
for (bit in 0 until 32) {
val mask = 1 shl bit
var countNums = 0
var countRange = 0
for (i in nums.indices) {
if (nums[i] and mask != 0) countNums++
if (i in 1..n && i and mask != 0) countRange++
}
if (countNums > countRange) {
result = result or mask
}
}
return result
}
}🔑 Takeaways#
- Pattern: 「陣列值當索引」可以將陣列問題轉化為鏈結串列/圖的問題，是一個強大的思維轉換
- 關鍵技巧: Floyd’s Algorithm 的兩階段法（找相遇點 + 找入口）不只用於鏈結串列，任何有「函數映射形成環」的問題都適用