Find the Duplicate Number

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

Note:

1. You must not modify the array (assume the array is read only).

2. You must use only constant, O(1) extra space.

3. Your runtime complexity should be less thanO(n^2).

4. There is only one duplicate number in the array, but it could be repeated more than once.

题目大意：

给定一个包含n + 1个整数的数组，其中每一个整数均介于[1, n]之间，证明其中至少有一个重复元素存在。假设只有一个数字出现重复，找出这个重复的数字。

注意：

1. 不可以修改数组（假设数组是只读的）

2. 只能使用常数空间

3. 运行时间复杂度应该小于O(n^2)

4. 数组中只存在一个重复数，但是可能重复多次

The first part of this problem - proving that at least one duplicate element must exist - is a straightforward application of the

pigeonhole principle.If the values range from 0 to n - 2, inclusive, then there are only n - 1different values. If we have an array of n elements, one must necessarily be duplicated.

这道题给了我们n+1个数，所有的数都在[1, n]区域内，首先让我们证明必定会有一个重复数，这不禁让我想起了小学华罗庚奥数中的抽屉原理(又叫鸽巢原理), 即如果有十个苹果放到九个抽屉里，如果苹果全在抽屉里，则至少有一个抽屉里有两个苹果，这里就不证明了，直接来做题吧。题目要求我们不能改变原数组，即不能给原数组排序，又不能用多余空间，那么哈希表神马的也就不用考虑了，又说时间小于O(n^2)，也就不能用brute force的方法，那我们也就只能考虑用二分搜索法了，我们在区别[1, n]中搜索，首先求出中点mid，然后遍历整个数组，统计所有小于等于mid的数的个数，如果个数大于mid，则说明重复值在[mid+1, n]之间，反之，重复值应在[1, mid-1]之间，然后依次类推，直到搜索完成，此时的low就是我们要求的重复值

Hashmap:

题目不让用多余的空间，所以不能用hash。

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hashmap = collections.Counter(nums)
        for item in hashmap:
            if hashmap[item] >= 2:
                return item

Binary Search:

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        start, end = 1, len(nums)-1
        while start+1<end:
            mid = (start+end)/2
            if self.numberOfsmall(nums, mid)<=mid:
                start = mid
            else:
                end = mid
        if self.numberOfsmall(nums,start)>start:
            return start
        return end

    def numberOfsmall(self, nums, mid):
        n = 0
        for num in nums:
                if num<=mid:
                    n += 1
        return n

快慢针（映射）：