[287][中等][双指针][二分] 寻找重复数

题目描述

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

• 不能更改原数组（假设数组是只读的）。

• 只能使用额外的 O(1) 的空间。

• 时间复杂度小于 O(n2) 。

• 数组中只有一个重复的数字，但它可能不止重复出现一次。

解题思路

双指针: 快慢指针

如果限定空间复杂度为$O(1)$, 就不能使用哈希表的思路. 再加上不能改变原数组, 堆排序的方法也就不可用了.

我们将题目给的数组以链表的角度来看, 链表的头是0, 代表指向数组的首位, 得到这个值num[0]之后, 下个数就是索引为num[0]对应的数组中的数num[num[0]], 依次类推, 串成一条链. 有因为数组中肯定有重复数, 重复的数都会指向同一个位置, 在第二次遇到这个重复数时, 继续向下就会遇到首次遇到这个重复数的下一个数, 从而形成了环, 之后就会重复下去.

例如数组[1,2,3,4,5,6,7,8,9,5], 循环下去就会得到1 2 3 4 5 [6 7 8 9] [6 7 8 9] [6 7 8 9]...这样的路径.

这样我们就从原题目中抽象出一个链表的构建方法, 接下来我们就要考虑的是判断这个链表有没有环, 如果有环, 找到这个环的起始点, 就找到了重复的数字, 因为重复的数字就在这个环起始点的前一个位置.

这样问题就变成了[142][中等][双指针] 环形链表 II, 在快慢指针第一次相遇后, 将其中一个指针重置为链表的首位, 即0, 然后两个指针以相同的速度每次后移一位, 直到对应的值相等, 这样我们就找到了这个重复值.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = nums[0], nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]

        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow

二分

Leetcode官方题解: 寻找重复数

使用二分法查找一个有范围的整数（结合抽屉原理）

二分法常常可以用于限定范围内的一个整数. 这道题要求我们查找的数是一个整数, 并且给出了这个整数的范围, 在1到n之间, 并且给出了一些限制, 于是可以使用二分查找法定位在一个区间里的整数.

二分法需要借助一个单调递增或递减的区间, 我们需要寻找这个空间. 对于任何一个数mid, 统计原始数组中小于等于这个中间数的元素的个数, 记为cnt, 如果cnt大于mid, 说明这个重复的数字在[left, mid]之间; 如果cnt不大于mid, 说明重复的数字在[mid+1, right]之间.

我们要做的就是用二分法不断的缩小区间范围, 每次对于所选的mid数字, 遍历整个原始数组, 统计原始数组中小于等于这个中间数的元素的个数, 决定下一步的区间选择策略. 整体的时间复杂度为$O(n \log n)$.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left, right = 1, len(nums) - 1
        while left < right:
            mid = (left + right) // 2

            cnt = sum([1 for num in nums if num <= mid])
            if cnt > mid:
                right = mid
            else:
                left = mid + 1
        return left

相关题目

• [41][困难][原地哈希] 缺失的第一个正数