# 287.Find the Duplicate Number 找到重复的数

## 刷题内容

• 中文：https://leetcode-cn.com/problems/find-the-duplicate-number
• 英文：https://leetcode.com/problems/find-the-duplicate-number

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。



## 解题方案

这个思路我们使用 二分查找（binary search）+ 鸽笼原理（Pigeonhole Principle）

"不允许修改数组" 与 "常数空间复杂度" 这两个限制条件意味着：禁止排序，并且不能使用 Map 等数据结构





... 同理3；4；5。


class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
low, high = 1, len(nums) - 1
while low <= high:
mid = (low + high) >> 1
cnt = sum(x <= mid for x in nums)
if cnt > mid:
high = mid - 1
else:
low = mid + 1
return low

s = Solution()
nums = [1,2,3,3]
print(s.findDuplicate(nums))

3


class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dic = dict()
for n in nums:
dic[n] = dic.get(n, 0) + 1
if dic[n] >= 2:
return n

s = Solution()
nums = [1,2,3,3]
print(s.findDuplicate(nums))

3


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.
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

s = Solution()
nums = [1,2,3,3]
print(s.findDuplicate(nums))

3


apachecn/AiLearning