題目描述
一個(gè)長度為n-1的遞增排序數(shù)組中的所有數(shù)字都是唯一的健芭，并且每個(gè)數(shù)字都在范圍0～n-1之內(nèi)摸柄。在范圍0～n-1內(nèi)的n個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在該數(shù)組中骚秦，請找出這個(gè)數(shù)字卸察。
題解
這道題目有兩個(gè)比較直觀的解脯厨，一個(gè)方法是從0開始順序遍歷數(shù)組，如果發(fā)現(xiàn)哪個(gè)位置不連續(xù)了坑质，則找到這個(gè)數(shù)字合武。另一個(gè)方法是將0 ~ n-1 的和減去數(shù)組的和，得到的結(jié)果就是缺失的數(shù)字涡扼。這兩種方法的時(shí)間復(fù)雜度都是O(n)稼跳。
其實(shí)時(shí)間復(fù)雜度為O(logn)的的二分法也是比較容易想到的，來看代碼吃沪。
class Solution {
public int missingNumber(int[] nums) {
int left = 0, right = nums.length-1, mid;
while (left < right) {
mid = (left + right) >> 1;
// 說明沒有問題汤善，缺失的數(shù)字在mid右邊
if (mid == nums[mid]) {
left = mid + 1;
}
// 說明缺失的數(shù)字在mid左邊
else if (mid < nums[mid]) {
right = mid - 1;
}
}
// 最終缺失的數(shù)字要么在left左邊，要么在left右邊
if (left < nums[left])
return nums[left] - 1;
return nums[left] + 1;
}
}
