n-1 java_【Java】 劍指offer(53-2) 0到n-1中缺失的數字

本文參考自《劍指offer》一書，代碼采用Java語言。

題目

一個長度為n-1的遞增排序數組中的所有數字都是唯一的，并且每個數字都在范圍0到n-1之內。在范圍0到n-1的n個數字中有且只有一個數字不在該數組中，請找出這個數字。

思路

分析易知，數組形式如下：

如果從頭到尾依次比較值與小標是否相等，時間復雜度為O(n)，效率低。

由于是排序數組，我們繼續考慮使用二分查找算法，結合上圖可知：

當中間數字等于其下標時，我們在后半部分查找；

當中間數字不等于其下標時，

1)如果中間數字的前一個數字也不等于其下標，則在前半部分查找；

2)如果中間數字的前一個數字等于其下標，則說明中間數字的下標即為我們所要找的數字。

測試算例

1.功能測試(缺失數字位于數組開頭、中間或者結尾)

2.邊界值測試(數字只有0或1)

2.特殊測試(null)

Java代碼

//題目：一個長度為n-1的遞增排序數組中的所有數字都是唯一的，并且每個數字

//都在范圍0到n-1之內。在范圍0到n-1的n個數字中有且只有一個數字不在該數組

//中，請找出這個數字。

public class MissingNumber {

public int getMissingNumber(int[] arr) {

if(arr==null || arr.length<=0)

return -1;

int low=0;

int high=arr.length-1;

while(low<=high) {

int mid=(low+high)>>1;

if(arr[mid]!=mid) {

if(mid==0 || arr[mid-1]==mid-1)

return mid;

high=mid-1;

}else {

low=mid+1;

}

}

if(low==arr.length)

return low;

return -1;

}

}

收獲