# LC 287 Find the Duplicate Number(M)

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

`public int findDuplicate(int[] nums)`

**边界条件** 如果只有一个值 返回0；

## 解题思路 2分查找， 或 环形查找

2分查找，根据抽屉原理，我们可以知道duplicate number 是在mid 的左边还是右边，以此类推，我们可以逐渐缩小范围，直至最后找到该duplicate number

```java
public int findDuplicate(int[] nums) {
    if(nums.length<2)
        return 0;
    int min = 0;
    int max = nums.length -1;
    while(min<= max){
        // 取 中值
        int mid = min + (max - min) /2;
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            ／／统计有多少小于中值
            if(nums[i]<=mid){
                count ++;
            }
        }
        if(count > mid){
            max = mid-1;
        }else{
            min = mid +1;
        }
    }
    return min;
}
```

环形查找 如果array 中所有的数都是不同的话，那么下标和数是一一对应的关系，否则，下标和数就是多对一的关系。这样的话，如果我们每次都把下标对应的那个数作为新的下标，那么它最后会变成一个环。根据这个环我们就可以找到重复的那个数。

```java
public int findDuplicate(int[] nums) {
    int slow = 0;
    int fast = 0;
    // 2倍快索 和一倍同时开始，直到相遇
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while(slow != fast);
    int find = 0;
    while (find != slow) {
        find = nums[find];
        slow = nums[slow];
    }
    return find;
}
```


---

# Agent Instructions: 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://tonyding.gitbook.io/algorithm/lc-287-find-the-duplicate-number.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.