给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1 到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

注意事项
1.不能修改数组(假设数组只能读)
2.只能用额外的O(1)的空间
3.时间复杂度小于O(n^2)
4.数组中只有一个重复的数，但可能重复超过一次

样例

给出 nums = [5,5,4,3,2,1]，返回 5.
给出 nums = [5,4,4,3,2,1]，返回 4.

分析

输入：int[]
输出：`int

数组为null`null`   
为空数组`int []{}`
[5,5,4,3,2,1]
[5,4,4,3,2,1]
[5,3,3,1,1,1]

```

### 思路

先考虑可以修改数组的查找方法。
1.排序后查找重复的数，这样的复杂度为O(NlogN)和O(1)
2.使用一个hash表，有碰撞时就可以找到重复的值 复杂度为O(NlogN)和O(N)

**可修改数组**
题目中描述整数从1到n，如果不在此范围内的任意数，也可以使用上面的方法，而有了范围的限定，可以考虑使用其他方法，查看是否可降低至O(N)
nums中包含n+1个整数，从1-n，如果排序后，数组中是1,2,3....n，可以看到数组的值为index+1，例如，nums = [5,5,4,3,2,1]，排序后为[1,2,3,4,5,5] 当nums[i]!=i时，说明有重复数据

```
public int findDuplicate(int[] nums) {
    if(nums == null||nums.length == 0) {
        return -1;
    }
    // 修改数组的方法 O(n)
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] - 1 != i) {
            int b = nums[i] - 1; // i所在的index
            int e = nums[b]; // i所在的index的值
            if (e == nums[i]) {
                return e;
            } else { // 不一样 swap i&b
                int tmp = nums[b];
                nums[b] = nums[i];
                nums[i] = tmp;
            }
        }
    }
    return 0;
}

```
**不可修改数组**
如果限定为不能修改数组，那么就不能排序了，哈希表还是可以使用的，复杂度为O(N)和O(N)；  
还可以使用计数法，从i=0开始，统计1-n中nums[i]的个数，复杂度为O(N^2)和O(1)；
可以考虑O(NlogN)和O(1),当时没有想出来，但是范围在1-n，可以考虑二分法，首先，数组n+1个元素，范围为1-n，因此肯定存在重复的数。可以先而分为[1，(n-1)/2+1]和[(n-1)/2+2，n],遍历数组，如果在范围内的数量大于范围的数量，如：[1，9]分为[1，5]和[6，9]，查找数组中[1，5]的数量，如果没有重复的，则数量为5，如果大于5说明[1，5]中有重复的值，然后在拆分为[1，3]和[4,5],再进行查找，复杂度为O(NlogN)和O(1)；

```
public int findDuplicate(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int min = 1;
    int max = nums.length - 1;
    while (true) {
        int mid = (max - min) / 2;
        mid = min + mid;
        int minSize = getSize(nums, min, mid);
        if (minSize > (mid - min + 1)) {
            if (mid == min) {
                return min;
            } else {
                max = mid;
                continue;
            }

        }
        int maxSize = getSize(nums, mid + 1, max);
        if (maxSize > (max - mid)) {
            if (mid + 1 == max) {
                return max;
            } else {
                min = mid + 1;
                continue;
            }
        }

    }
}

public int getSize(int a[], int min, int max) {
    int ret = 0;
    int count = max - min + 1;
    for (int i = 0; i < a.length; i++) {
        if (a[i] >= min && a[i] <= max) {
            ret++;
            if (ret > count) {
                return ret;
            }
        }
    }
    return ret;
}

```