难度: Medium
原题连接
内容描述
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.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
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.
思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(1)******
参考小瑶大神的思路
二分枚举答案范围，使用鸽笼原理进行检验
根据鸽笼原理，给定 n+1 个范围为 [1, n]的整数，其中一定存在数字出现至少两次。 假设枚举的数字为 n / 2 ： 遍历数组，若数组中不大于 n / 2 的数字个数超过 n / 2 ，则可以确定 [1, n/2] 范围内一定有解，否则可以确定解落在 (n/2, n]范围内。 也可以这样分析一下：
如果n 是5，那么就会有1 2 3 4 5 一共5个数字的可能，而array size 是6，那么其中一个数字肯定会至少出现两次。
如果没有重复的数字，小于等于1的数字 出现的次数 等于 1；
小于等于2的数字 出现的次数 等于 2；
... 同理3；4；5。
如果有重复的数字，如果重复的是1，那么 小于等于1的数字 出现的次数 肯定大于1；
基于这个理论，我们可以在1 2 3 4 5 选出一个 mid， 遍历array来count 小于等于mid 的数字个数 小于等于 它自己mid 还是 大于 mid？
如果count 小于等于mid， 说明 1 到 mid 这些数字 没有重复项， 重复项在 右半边 mid 到n， 所以缩小到右半边继续搜索；
如果count 大于mid， 说明 1 到 mid 这些数字中 有重复项，缩小到 左半边继续搜索。
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l, r = 0, len(nums) - 1
while l <= r:
mid = l +((r-l) >> 2)
count = sum(num <= mid for num in nums)
if count > mid:
r = mid - 1
else:
l = mid + 1
return l思路 2 - 时间复杂度: O(NlgN)- 空间复杂度: O(1)******
参考haitao7大神的思路
我们可以用bit的思路来做，basic idea就是，重复出现的那个数字会使得我们在某一位上出现1的次数是异常的
比如说[1,3,4,2,2]跟[1, 2, 3, 4]对比：
- [1, 3, 4, 2, 2] == [001, 011, 100, 010, 010]
- [1, 2, 3, 4] == [001, 010, 011, 100]
从最小位开始看起，[1, 3, 4, 2, 2]有2个数，1和3，在最小位上是1，[1, 2, 3, 4]也一样。
但是在从右往左数第二位，[1, 3, 4, 2, 2]就有3个数[3, 2, 2] == [011, 010, 010]，在那个bit上是1；而[1, 2, 3, 4]只有[2, 3]两个。
每当发现一个数位上，nums里在那个数位上为1的元素个数，超过了1到n在那个数位上为1的元素个数，我们就可以确定，重复的那个数，在那个数位上肯定是1。如果数位上的1个数相等，则本来那个重复的数字该数位上也是0，不管重复的那个数重复出现多少次，只要多了该数位就是1，没多该数位就是0。
这个算法还是有点慢，可能大家用的都是接下来的这个思路，只beats 了 2%
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
import math
bits_count = int(math.log(len(nums), 2)) # this is the bits we have
base, duplicate = 1, 0
for i in range(bits_count+1): # O(logn) for loop
normal, real = 0, 0
for j in range(len(nums)): # O(n) for loop
normal += (j >> i) & 1
real += (nums[j] >> i) & 1
if real > normal:
duplicate += base
base <<= 1
return duplicate思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******
快慢指针，先快慢轮询一遍，再慢慢轮询一遍，就找到了，beats 99.7%
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# The "tortoise and hare" step. We start at the end of the array and try
# to find an intersection point in the cycle.
slow, fast = 0, 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