# LeetCode----Find the Duplicate Number

Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number,
find the duplicate one.

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than

`O(n2)`
.
There is only one duplicate number in the array, but it could be repeated more than once.

`class Solution(object): def findDuplicate(self, nums):""":type nums: List[int]:rtype: int"""slow, fast = 0, 0while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast:break# fast和slow一定在循环中某点相遇了，但是相遇的点不一定是刚刚进入循环的那个元素，# 需要从0开始继续寻找find = 0while find != slow: slow = nums[slow] find = nums[find]return find`

`class Solution(object): def findDuplicate(self, nums):""":type nums: List[int]:rtype: int"""l, r = 0, len(nums) - 1while l <= r: mid = l + (r - l) / 2 cnt = 0 for n in nums:if n <= mid: cnt += 1 if cnt > mid:r = mid - 1 else:l = mid + 1return l`