题目:
分析:
- 解法一: 哈希表
- 解法二: 直接遍历
- 解法三: 位运算
- 解法四: 高斯求和公式(数学)
- 但是上述的解法, 时间复杂度都是O(n)
- 解法五: 二分查找
- 观察: 以示例一为例: 消失的数字是4, 其左边0, 1, 2, 3 对应的下标也是0, 1, 2, 3, 值等于下标, 其右边5, 对应的下标是4, 值大于下标, 所以具有"二段性", 可以使用二分查找
- 如果mid == records[mid] 说明消失的数字在右边, 移动左指针left = mid + 1
- 如果mid < records[mid], 说明消失的数字的下标可能是mid, 也可能在mid左边, 移动右指针right = mid
- 所以匹配二分查找算法的模版二, mid = left + (right-left) / 2
- 处理细节: 如果最后缺失的数字是最后一个数字, 左右指针在最后一个位置相遇, 并不是最终的结果, 那么应该返回+1的位置
代码:
class Solution {
public int takeAttendance(int[] records) {
int left = 0;
int right = records.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mid == records[mid])
left = mid + 1;
else
right = mid;
}
if (records[left] == left)//处理细节
return left + 1;
return left;
}
}