題目描述
給定一個包含 n + 1 個整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n）淆游，可知至少存在一個重復(fù)的整數(shù)傍睹。假設(shè)只有一個重復(fù)的整數(shù)，找出這個重復(fù)的數(shù)犹菱。
示例 1:
輸入: [1,3,4,2,2]
輸出: 2
示例 2:
輸入: [3,1,3,4,2]
輸出: 3
說明：
不能更改原數(shù)組（假設(shè)數(shù)組是只讀的）拾稳。
只能使用額外的 O(1) 的空間。
時間復(fù)雜度小于 O(n2) 已亥。
數(shù)組中只有一個重復(fù)的數(shù)字熊赖，但它可能不止重復(fù)出現(xiàn)一次。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有虑椎。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)震鹉，非商業(yè)轉(zhuǎn)載請注明出處。
解題思路
這一題有兩個解法都是是很奇妙
鏈表環(huán) 快慢指針
class Solution(object):
def findDuplicate(self, nums):
# The "tortoise and hare" step. We start at the end of the array and try
# to find an intersection point in the cycle.
slow = 0
fast = 0
# Keep advancing 'slow' by one step and 'fast' by two steps until they
# meet inside the loop. they may step i loops,slow step n steps ,fast step 2*n ,each loop have n/i steps
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Start up another pointer from the end of the array and march it forward
# until it hits the pointer inside the array.
finder = 0
while True:
slow = nums[slow]
finder = nums[finder]
# If the two hit, the intersection index is the duplicate element.
if slow == finder:
return slow
作者：Damien_Undo
鏈接：https://leetcode-cn.com/problems/two-sum/solution/kuai-man-zhi-zhen-yuan-li-jian-yi-jie-shi-by-damie/
來源：力扣（LeetCode）
著作權(quán)歸作者所有捆姜。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)传趾，非商業(yè)轉(zhuǎn)載請注明出處。
二分查找
關(guān)鍵是對數(shù)得范圍二分泥技，而不是對數(shù)組得索引二分浆兰。
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
left = 1
right = len(nums)-1
while left < right :
mid = left+ (right -left) //2
count = 0
for i in range(len(nums)):
if nums[i] <= mid:
count +=1
if count > mid :
right = mid
else:
left = mid +1
return left
