# 0287. Find the Duplicate Number
###### tags: `Leetcode` `Medium` `Indexing Sort`
Link: https://leetcode.com/problems/find-the-duplicate-number/
## 思路
类似[0442. Find All Duplicates in an Array](https://hackmd.io/UnpI8ph4Q6icK2K1UxDHfg)
**注意： 不能用异或是因为，input case里面可能有[2,2,2,2,2]，不一定都是里面装了1，2，3，4的array**
### 思路一 $O(N)$ $O(N)$
set
### 思路二 $O(N)$ $O(1)$
**Negative Marking**
There are n+1 positive numbers in the array (nums) (all in the range [1,n]). Since the array only contains positive integers, we can track each number (num) that has been seen before by flipping the sign of the number located at index |num|, where || denotes absolute value.

For example, if the input array is [1,3,3,2], then for 1, flip the number at index 1, making the array [1,-3,3,2]. Next, for −3 flip the number at index 33, making the array [1,−3,3,−2]. Finally, when we reach the second 3, we'll notice that nums[3] is already negative, indicating that 3 has been seen before and hence is the duplicate number.
### 思路三 $O(N)$ $O(1)$
in-place变换
就是把每个数字num，放在nums[num-1]，也就是让nums[num-1] = num, 如果nums[num-1]已经等于num了，还想往nums[num-1]里面放数字，就说明有重复了
### 思路四 $O(N)$ $O(1)$ without modifying original array
因为有重复的数字，所以用index找数字，一定会有circle
而能进到circle的entry就是duplicate number
假如nums[i] = a nums[j] = a 也就是nums[i]可以走到nums[a]，一定有一条路径可以让nums[i]走到nums[j]，然后就会又回到nums[a]
An explanation about finding the entry point part.
First assume when fast and slow meet, slow has moved $a$ steps, and fast has moved $2a$ steps. They meet in the circle, so the difference $a$ must be a multiple of the length of the circle.
Next assume the distance between beginning to the entry point is $x$, then we know that the slow has traveled in the circle for $a-x$ steps.
How do we find the entry point? Just let slow move for another $x$ steps, then slow will have moved $a$ steps in the circle, which is a multiple of length of the circle.
So we start another pointer at the beginning and let slow move with it. Remember $x$ is the distance between beginning to the entry point, after $x$ steps, both pointer will meet at the entry of circle.

## Code
### 思路二

class Solution {
    public int findDuplicate(int[] nums) {
        int duplicate = -1;
        for(int i = 0;i < nums.length;i++){
            int cur = Math.abs(nums[i]);
            if(nums[cur]>0){
                nums[cur]*=-1;
            }
            else{
                duplicate = cur;
                break;
            }
        }
        for(int i = 0;i < nums.length;i++){
            nums[i] = Math.abs(nums[i]);
        }
        return duplicate;
    }
}

### 思路三

class Solution {
    public int findDuplicate(int[] nums) {
        int[] arr = nums;
        for(int i = 0;i < arr.length;i++){
            if(arr[i] == i+1) continue;
            while(arr[i] != i+1){
                int num = arr[i];
                if(arr[num-1] == num) return num;
                swap(arr, i, num-1);
            }
        }
        return 0;
    }
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

### 思路四

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while(slow!=fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while(fast!=slow){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}