跳至主要內容

0287. 寻找重复数

ITCharge大约 1 分钟

0287. 寻找重复数open in new window

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

题目链接

题目大意

描述:给定一个包含 n+1n + 1 个整数的数组 numsnums,里边包含的值都在 1n1 \sim n 之间。可知至少存在一个重复的整数。

要求:假设 numsnums 中只存在一个重复的整数,要求找出这个重复的数。

说明

  • 1n1051 \le n \le 10^5
  • nums.length==n+1nums.length == n + 1
  • 1nums[i]n1 \le nums[i] \le n
  • 要求使用空间复杂度为常数级 O(1)O(1),时间复杂度小于 O(n2)O(n^2) 的解决方法。

示例

  • 示例 1:
输入:nums = [1,3,4,2,2]
输出:2
  • 示例 2:
输入:nums = [3,1,3,4,2]
输出:3

解题思路

思路 1:二分查找

利用二分查找的思想。

  1. 使用两个指针 leftleftrightrightleftleft 指向 11rightright 指向 nn
  2. 将区间 [1,n][1, n] 分为 [left,mid][left, mid][mid+1,right][mid + 1, right]
  3. 对于中间数 midmid,统计 numsnums 中小于等于 midmid 的数个数 cntcnt
  4. 如果 cntmidcnt \le mid,则重复数一定不会出现在左侧区间,那么从右侧区间开始搜索。
  5. 如果 cut>midcut > mid,则重复数出现在左侧区间,则从左侧区间开始搜索。

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度O(n×logn)O(n \times \log n)
  • 空间复杂度O(1)O(1)