0287. 寻找重复数 #

标签：位运算、数组、双指针、二分查找
难度：中等

题目大意 #

给定一个包含 n+1 个整数的数组 nums，里边包含的值都在 1~n 之间。假设 nums 中只存在一个重复的整数，要求找出这个重复的数。

要求使用空间复杂度为常数级 O(1) ，时间复杂度小于 $O(n^2)$ 的解决方法。

解题思路 #

利用二分查找的思想。用两个指针 left，right。left 指向 1，right 指向 n。将区间 [1, n] 分为 [left, mid] 和 [mid + 1, right] 。对于中间数 mid，统计 nums 中小于等于 mid 的数个数 cnt。如果 cnt 小于等于 mid，则重复数一定不会出现在左侧区间，那么从右侧区间开始搜索。若 cut 大于 mid，则重复数出现在左侧区间，则从左侧区间开始搜索。

代码 #

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


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        left = 1
        right = n - 1
        while left < right:
            mid = left + (right - left) // 2
            cnt = 0
            for num in nums:
                if num <= mid:
                    cnt += 1

            if cnt <= mid:
                left = mid + 1
            else:
                right = mid

        return left