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

## 题目描述

[287. 寻找重复数](https://leetcode-cn.com/problems/find-the-duplicate-number/)

给定一个包含 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](https://blessbingo.gitbook.io/garnet/suan-fa/shuang-zhi-zhen/142-huan-xing-lian-biao-ii), 在快慢指针第一次相遇后, 将其中一个指针重置为链表的首位, 即0, 然后两个指针以相同的速度每次后移一位, 直到对应的值相等, 这样我们就找到了这个重复值.

```python
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官方题解: 寻找重复数](https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/)

[使用二分法查找一个有范围的整数（结合抽屉原理）](https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-si-lu-ji-dai-ma-python-by-liweiwei1419/)

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

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

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

```python
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\]\[困难\]\[原地哈希\] 缺失的第一个正数](https://blessbingo.gitbook.io/garnet/suan-fa/ha-xi/41-que-shi-de-di-yi-ge-zheng-shu)