# \[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](broken://pages/-MI7NbgqSu3sPOa8iTTY), 在快慢指针第一次相遇后, 将其中一个指针重置为链表的首位, 即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\]\[困难\]\[原地哈希\] 缺失的第一个正数](broken://pages/-MI7NbhMQjoJe1OIqkaz)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/shu-zu/287-xun-zhao-zhong-fu-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.