算法2: 二分查找 + 鸽笼原理

利用鸽笼原理, 如果统计左半区间(l到mid)元素的个数, 如果超过了区间的长度, 那么这个左半区间必然存在重复元素.
如果没有超过区间长度, 那么右半区间必然存在重复元素.

时间复杂度

时间复杂度为O(n * log(n))
空间复杂度为O(1)

Python 代码

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        n = len(nums) - 1
        l, r = 1, n
        while l < r:
            mid = (l + r) >> 1
            cnt = 0
            for e in nums:
                if l <= e <= mid:
                    cnt += 1
            if cnt > mid - l + 1:
                r = mid
            else:
                l = mid + 1
        return l

算法2: 位运算

通过整数型变量, 记录下哪些数字出现过

时间复杂度

时间复杂度为O(n)
空间复杂度为O(n)

Python 代码

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        vis = 0
        for e in nums:
            if (vis >> e) & 1:
                return e
            else:
                vis ^= 1 << e