题目
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
解答
# 二分解法符合要求。以数组长度为范围进行二分。Time: O(nlogn)， Space: O(1)
class Solution:
def findDuplicate(self, nums):
left, right = 1, len(nums)-1
mid = (left + right) // 2
while right != mid: # log(n)
if self.get_cnt(nums, left, mid) > (mid-left+1):
right = mid
else:
left = mid + 1
mid = (left + right) // 2
return mid
def get_cnt(self, nums, left, right):
cnt = 0
for x in nums: # O(n)
if x >= left and x <= right:
cnt += 1
return cnt
# 其他解法：
# 1, sort() Time: O(nlogn), Space: O(1) 有修改
# 2, 交换 Time: O(n), Space: O(1) 有修改
# 3, 哈希表 Time: O(n), Space: O(n) 无修改
其他解法参考代码：
# 交换
class Solution:
def findDuplicate(self, nums):
length = len(nums)
for index in range(length):
while nums[index] != nums[nums[index]-1]: # 均摊为O(1)
temp = nums[index]
nums[index], nums[temp-1] = nums[temp-1], nums[index]
for index, x in enumerate(nums):
if index+1 != x:
return x
# hash table
class Solution:
def findDuplicate(self, nums):
s = set()
for x in nums:
if x not in s:
s.add(x)
else:
return x
# sort()
class Solution:
def findDuplicate(self, nums):
nums.sort()
for index, x in enumerate(nums):
if x == nums[index+1]:
return x