【done】剑指 Offer 53 - II：0～n-1中缺失的数字

力扣，https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

solution1

线性扫描，一般情况

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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也可
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17