当代菜鸡的男友:复杂度O(logN) ,二分查找。 总结规律:缺失位置之前的元素值比其下标大1,缺失位置之后的元素值比其下标大2。 如果当前元素的值比其下标大1,则缺失元素 > 当前元素,到当前元素后面去找; (ps: 这里有一种特殊情况,当前元素为最后一个元素的时候) 如果当前元素的值比其下标大2,则缺失元素 < 当前元素,到当前元素前面去找。 public int getNotFoundNumber(int[] data) {
int start = 0, end = data.length-1;
int mid;
while (start end) {
mid = (start + end)/2;
if (data[mid] - mid == 1) {
if (mid == 98) {
return 100;
}
start = mid + 1;
}
if (data[mid] - mid == 2) {
end = mid - 1;
}
}
return data[start] - 1;
}
投递OPPO等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了: