【重点】【二分搜索】剑指 Offer 53 - II:0~n-1中缺失的数字

力扣,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也可
    }
}
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值