53-Ⅱ.0~n中缺失的数字

参考链接

剑指offer_在线编程_牛客网

剑指 Offer 53 – II. 0～n-1中缺失的数字-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

LCR 173. 点名 - 力扣（LeetCode）

个人尝试

二分查找，通过数组的 mid 下标 与 mid下标对应的数组元素 的对比来查找结果

倘若缺失元素，会导致 mid 下标 < records[mid]，因为 缺失的元素会被后面更大的元素填补上

倘若不缺失元素，则 mid 下标 == records[mid] ，则缺失的元素可能在后半段

最终结果需要通过 left 下标 来确定

class Solution {
    public int takeAttendance(int[] records) {
        int left = 0;
        int right = records.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (mid < records[mid]) right = mid - 1;
            // mid == records[mid]
            else left = mid + 1;
        }
        return left;
    }
}

优秀题解

class Solution {
    public int takeAttendance(int[] records) {
        int i = 0, j = records.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(records[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/solutions/155915/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。