# 287. Find the Duplicate Number

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:\
> 1\. You must not modify the array (assume the array is read only).\
> 2\. You must use only constant, O(1) extra space.\
> 3\. Your runtime complexity should be less than O(n^2).\
> 4\. There is only one duplicate number in the array, but it could be repeated more than once.

## Thoughts

容易想到暴力法嵌套遍历时间复杂度O(n^2). 可以用hashset先把出现过的数字记下来，但这样空间复杂度为O(n)，不符合题目要求。\
可以先排序，然后再遍历配合二分。但排序算法必须是heapsort才满足O(1)空间复杂度和O(nlgn)时间复杂度。\
那有没有不用排序就能二分的解法呢？没想出来。。

后来看到别人分享的后恍然大悟。做不出来最主要原因是 **审题不清** 。题目里有一句很重要的each integer is between 1 and n (inclusive)没在意。

但即使注意到了，想用二分法做对还是不容易。因为它用到的关系为：不重复时数组中小于等于mid的数字数目应等于mid。\
因此本题的二分不同寻常之处在于它的mid是index时，择半规则直接用的mid却不是用nums\[mid]。\
相应的，返回的也直接是start/end而不是nums\[start/end].\
除此之外，它的二分法放在了外循环。

## Code

```java
class Solution {
    public int findDuplicate(int[] nums) {
        int start = 1, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                     count++;
                }
            }

            if (count <= mid) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}
```

## Analysis

时间复杂度为O(nlgn), 空间复杂度O(1).

## Ver.2

如果没有重复的并把数组每个元素看成是指针，从0开始蹦会类似在linked list上遍历，最后蹦出数组。当有重复元素时形成环，找环起始用检测环的Floyd算法：快慢指针。还可以阵对元素值对相应位置取负作为标记，当取负时发现已经是负数的也就是答案。

```cpp
/*
* @lc app=leetcode id=287 lang=cpp
*
* [287] Find the Duplicate Number
*/

// @lc code=start
class Solution {
public:
   int findDuplicate(vector<int>& nums) {
       int slow = 0, fast = 0;
       while (true) {
           slow = nums[slow]; 
           fast = nums[nums[fast]];
           if (slow == fast) break;
       } 
       int head = 0;
       while (slow != head) {
           slow = nums[slow];
           head = nums[head];
       }
       return head;
   }
};
// @lc code=end
```