力扣,https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
二分搜索
class Solution:
def takeAttendance(self, records: List[int]) -> int:
l, r = 0, len(records) - 1
while l <= r: # 退出循环的条件: l == r+1
mid = (l+r) // 2
if records[mid] == mid: # 答案肯定在[mid+1, r]之内
l = mid + 1
elif records[mid] > mid: # 答案可能是mid, 但r=mid会有死循环, 所以r=mid-1
r = mid - 1
# 显然不会出现 records[mid] < mid 的情况
return l
Java
线性扫描,一般情况
class Solution {
public int takeAttendance(int[] records) {
boolean[] visited = new boolean[records.length + 1];
Arrays.fill(visited, false);
for (int i : records) {
visited[i] = true;
}
for (int i = 0; i < visited.length; ++i) {
if (!visited[i]) {
return i;
}
}
return -1;
}
}
solution2
二分搜索
class Solution {
public int takeAttendance(int[] records) {
return binarySearch(0, records.length - 1, records);
}
public int binarySearch(int left, int right, int[] records) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (records[mid] == mid) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;// 返回right + 1也可
}
}