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.

Solution

• 根据鸽笼原理，给定n + 1个范围[1, n]的整数，其中一定存在数字出现至少两次。

• 假设枚举的数字为 n / 2：

• 遍历数组，若数组中不大于n / 2的数字个数超过n / 2，则可以确定[1, n /2]范围内一定有解，

• 否则可以确定解落在(n / 2, n]范围内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 1 # 从１开始枚举，题目要求
        r = len(nums)-1

        while l <= r:
            m = (l+r)/2

            # 计算不大于m的个数，m 不是位置，而是枚举的数字
            sums = sum(x<=m for x in nums)
            if sums > m:
                r = m-1
            else:
                l = m+1
        return l