在一個(gè)長度為 n+1 的數(shù)組李所有的數(shù)字都在 1~n 的范圍內(nèi)。請(qǐng)找出數(shù)字中任意一個(gè)重復(fù)的數(shù)字谈飒，但不能修改輸入的數(shù)組岂座。
解：
時(shí)間復(fù)雜度為 O(n*logn)，空間復(fù)雜度為 O(1)杭措。
但該算法不能保證找出所有重復(fù)的數(shù)字费什。如 {2, 3, 5, 4, 3, 2, 6, 7} 中找不到重復(fù)的數(shù)字 2。
// 驗(yàn)證數(shù)組輸入的正確性
public static boolean validateArray(int[] array) {
if (array == null || 0 == array.length)
return false;
for (int i = 0; i < array.length; i++) {
if (array[i] < 1 || array[i] > array.length)
return false;
}
return true;
}
public static int getDuplication(int[] array) {
if (validateArray(array)) {
// 數(shù)組內(nèi)的所有數(shù)字都在 1 到 array.length - 1 的范圍內(nèi)
int start = 1;
int end = array.length - 1;
// 二分法手素，當(dāng) start == end 時(shí)退出循環(huán)鸳址，此時(shí) start 的值就是出現(xiàn)重復(fù)的值
while (start != end) {
// 求中間的數(shù)字
int middle = (end + start) >> 1;
// 記錄從 start 到 middle 的數(shù)字在數(shù)組中出現(xiàn)的次數(shù)
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] >= start && array[i] <= middle)
count++;
}
// 與“n 中有 n + 1 個(gè)數(shù)字瘩蚪，則必有一個(gè)數(shù)字是重復(fù)的”同理
if (count > middle - start + 1)
end = middle;
else
start = middle + 1;
}
return start;
}
return -1;
}
