給出一個數組 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;
}
```