题解 | #缺失数字#
缺失数字
http://www.nowcoder.com/practice/9ce534c8132b4e189fd3130519420cde
既然要求了O(n)时间复杂度尽可能小，那么面试如果遇到可能要用二分啊！这个是考点啊！否则直接就：好，今天面试结束了！
int solve(vector<int>& a) {
// write code here
int length = a.size();
if(length <=0 )
return -1;
int start = 0;
int end = length - 1;
int mid = (start + end)/2;
while(1)
{
if(start >= end)
{
//找到的数—1 或者 +1
if(a[start] > start)
return start;
else
return start+1;
}
else if(mid == a[mid])
{
start = mid + 1;
mid = (start + end)/2;
}
//确实数字在左边
else
{
end = mid - 1;
mid = (start + end)/2;
}
}
}</int>
