0287. 寻找重复数

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
本站总访问量  次  |  您是本站第  位访问者