leetcode LCR 173. 点名

2023-12-16 11:53:29

代码:

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

            if(mid==records[mid]){
                left=mid+1;
            }else {
                right=mid;
            }
        }

        if(left==records[left]){
            return left+1;
        }else {
            return left;
        }
    }
}

题解:

? ? ? ? 该题有很多种解决方法,但大多数的解决方法都是 O( N ) 的复杂度,这里介绍一种 O(log? ? N)的方法,二分法

? ? ? ? 题目的含义很简单,这里直接通过 records = 0,1,2,4,5 来介绍,我们把每个数据对应的下标标出,很容易发现数组可以被分为两个区间,左区间的下标与值对应相等,右区间的值和下标不相等

????????缺席的数据是 3 ,我们很容易发现 3 就是右区间左边界的下标,所以我们的目标就是找到右区间的左边界的下标

【0? ? ? ? 1? ? ? ? 2】【4? ? ? ? 5】

? ?0? ? ? ? ?1? ? ? ? 2? ? ? ?3? ? ? ? 4

? ? ? ? 我们任意取一个数 records[ i ],当 records[ i ] 的值和下标相等时,说明 records[ i ] 在左区间,左区间中没有我们想要的结果,所以我们可以大胆去除 records[ i ] 以及 records[ i ] 左边的数据,当 records[ i ] 的值和下标不等时,说明该数在右区间,我们可以大胆去除 records[ i ] 右边的数据(不能去除 records[ i ] ,因为我们不确定是否 records[ i ] 就是我们要找的左边界)

? ? ? ? 从上面的分析我们可以看出,该题具有二段性,可以根据一定条件去除一部分数据,所以我们可以用二分法来解决该问题

? ? ? ? 依然用上述数据进行模拟

? ? ? ? 让 L 和 R 指针指向数组的两端,计算中点 mid = L +(R - L)/2 = 2,此时 records[ mid ] =mid ,所以在左区间,我们可以让 L = mid +1

【0? ? ? ? 1? ? ? ? 2】【4? ? ? ? 5】

? ?0? ? ? ? ?1? ? ? ? 2? ? ? ?3? ? ? ? 4

? ?L? ? ? ? ? ? ? ? ? mid? ? ? ? ? ? ? R

? ? ? ? 再计算中点 mid = L +(R - L)/2 = 3,此时 records[ mid ] != mid,所以在右区间,让 R = mid

【0? ? ? ? 1? ? ? ? 2】【4? ? ? ? 5】

? ?0? ? ? ? ?1? ? ? ? 2? ? ? ?3? ? ? ? 4

? ????????????????????????????? ?L? ? ? ? R

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?mid

? ? ? ? 当 L 和 R 相遇时,我们便得到了要找的结果

【0? ? ? ? 1? ? ? ? 2】【4? ? ? ? 5】

? ?0? ? ? ? ?1? ? ? ? 2? ? ? ?3? ? ? ? 4

? ????????????????????????????? ?L? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R

? ? ? ? 要注意一种特殊情况,当输入的?records = 0,1,2,3,4 时,对应的下标也是 0,1,2,3,4 ,此时下标和值一直都是对应相等的,所以一直都处于左区间,这就会导致当 L 和 R 相遇在数组的最后一个数据 4 上,对应的下标也为 4 ,但我们要填充的是 5 ,所以要判断一下,当 L 和 R 指针相遇时,如果?records[ L ] == L ,就返回 L +1,否则返回 L

文章来源:https://blog.csdn.net/q322359/article/details/135004530
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。