LCR 173. 点名 - 力扣（LeetCode）

此题有不同的几种解法：

解法一：暴力枚举  O(n);

解法二：哈希表       把原数组丢入哈希表，遍历哈希表，看看哪个数值为0即可。 O(n)空间+O(n)时间

解法三：位运算       搞一个和原数组大小相同的数组，和原数组进行异或，最后看看剩下是哪一个数即可。                O(n)空间+O(n)时间

解法四：高斯求和    求和公式算出结果后，依次 - 数组中的元素，被减数剩下的就是结果。O(n)

解法五：二分查找 

   

可以看出，数组和下标的对应关系，右区间的左端点对应的下标，就是缺的那个数字。

所以此题采用求区间左端点的方法解决。

细节问题

1.处理边界情况：如果数组缺的正好是最后一个位置，那么需要特殊处理。

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