leetcode LCR 173. 点名

代码：

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