0~n-1中缺失的數(shù)
- 一個(gè)長(zhǎng)度為n -1的遞增排序數(shù)組中的所有數(shù)字都是唯一的吓肋，并且每個(gè)數(shù)字的都在范圍0~n-1之內(nèi)。
- 在范圍內(nèi)0~n-1內(nèi)的n個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在該數(shù)組中，找出這個(gè)數(shù)字
思路一：
分別計(jì)算0-n-1的和n*(n-1)/2
* 和數(shù)組和
* 求差
思路二：
我們知道抑片，在缺失的元素出現(xiàn)前基括，每一個(gè)數(shù)都和數(shù)組元素的下標(biāo)相等，由于一個(gè)位置缺失了元素年堆，所以下一個(gè)位置的元素出現(xiàn)在其位置上，于是問(wèn)題可以轉(zhuǎn)化為找出第一個(gè)元素和下標(biāo)不相等的位置的索引盏浇。
利用二分法查找变丧，如果當(dāng)前位置元素和索引不相等，并且前一個(gè)元素也不相等绢掰，則去左邊尋找痒蓬，相等則返回元素童擎。如果當(dāng)前位置元素與索引相等則去右邊尋找。
代碼如下：
/**
* 二分查找
* @param array
* @return
*/
public int findLoss(int[] array) {
if (array == null) return -1;
int low = 0;
int len = array.length;
int high = len -1;
while (low <= high){
int mid = (low+high)>>1;
if (mid != array[mid]){
if (mid == 0 || mid-1 == array[mid-1]){
return mid;
}else {
high = mid-1;
}
}else {
low = mid + 1;
}
}
if (low == len) return len;
// 無(wú)效的輸入數(shù)組攻晒，如不是遞增排序顾复，或者有的數(shù)字超出了0~n-1的范圍
return -1;
}
