给出一个数组 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;
}
```
