一.题目描述

LCR 173. 点名 - 力扣（LeetCode）

二.题目解析

有0~n-1这n个数，但是数组中只有n-1个数，我们要找到消失的那个数。

三.算法原理

1.哈希表

我们先创建一个n个数的哈希表并初始化为0，然后将数组中的数存放到哈希表中，然后遍历哈希表，找到那个value为0的key，返回key即可。

2.直接遍历

学号是从0~n-1，数组的下标也是从0开始，所以学号和数组的下标是相同的。如果我们在遍历的过程中遇到下标和学号不相等，说明这里就缺少了一个数。而数组的下标是严格递增的，所以当前位置的下标就是缺失的数字。

边界情况：如果我们缺少的是最后一个数，在遍历的过程中，不会退出循环，直到循环结束。此时下标i就是结果。为什么呢？一共有0~n-1这n个数，数组有n-2个数，数组的下标与学号是统一的，说明0~n-2个数都在数组中，那么缺少的数就是n-1。而此时退出循环，i刚好就是n-1，所以我们返回下标即可。

3.位运算

我们可以将该题转化成“单身狗”问题。我们可以用一个变量ret = 0，与数组的每一个元素异或，然后再与0~n-1这n个数异或，此时异或后的结果就是缺失的数字。

4.利用数学公式

我们先将0~n-1这n个数的和求出来，然后减去数组的和，剩下的就是丢失的数

5.二分查找算法

我们观察数组元素与其下标之间的关系：

数组下标与其元素要么相等，要么不相等，这个性质就将数组分为了两端，此时数组呈现出二段性，我们就可以使用二分查找算法来解决。

 我们观察上图可以发现，在根据二段性分成的两个区间中，右区间的左端点的下标就是缺失的数，所以我们要寻找右区间的左端点。

 但是我们需要注意边界情况：如果数组的下标和元素都是一一对应的，那么此时left和right会在数组的结束位置，但此时的下标并不是结果，下标+1才是结果。

此时我们需要判断，如果结束位置的下标和元素相等，那么就是遇到了边界情况，返回下标+1. 

对上面算法的时间和空间复杂度进行分析：

时间复杂度：1~4这几种算法本质上都至少要遍历一次数组，所以其时间复杂度为O(N)，而二分算法每一次可以排除一半的数据，所以其时间复杂度为O(logN)

空间复杂度：法一哈希表的方式开了一个大小为n的数组用来模拟哈希表，所以它的空间复杂度为O(N)，其他算法的空间复杂度都为O(1) 

四.代码实现

python代码只给出最优的二分写法

// C++

class Solution
{
public:
    //法一：哈希表
    int takeAttendance(vector<int>& records)
    {
        int ret = -1;
        vector<int> v(records.size() + 1, 0);
        for (auto e : records)v[e] = 1;

        for (int i = 0; i < v.size(); ++i)
        {
            if (v[i] == 0) ret = i;
        }
        return ret;
    }

    //法二：直接遍历
    int takeAttendance(vector<int>& records)
    {
        int i = 0;
        for (i = 0; i < records.size(); ++i)
        {
            if (i != records[i]) break;
        }
        return i;
    }

    //法三：位运算——单身狗
    int takeAttendance(vector<int>& records)
    {
        int ans = 0;
        for (auto e : records) ans ^= e;
        for (int i = 0; i < records.size() + 1; ++i) ans ^= i;
        return ans;
    }

    //法四：数学求和公式
    int takeAttendance(vector<int>& records)
    {
        int n = records.size() + 1; // 总数
        int ret = (0 + n - 1) * n / 2;
        for (int i = 0; i < records.size(); ++i) ret -= records[i];
        return ret;
    }

    //法五：二分查找算法
    int takeAttendance(vector<int>& records)
    {
        int left = 0;
        int right = records.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        //细节问题：left走到右端点后，有可能数组完全有序：[0,1,2,3]，此时我们要返回的是left+1
        //其他情况，下标就是结果
        if (left == records[left]) return left + 1;
        return left;
    }
};

# python

class Solution:
    def takeAttendance(self, records: List[int]) -> int:
        left,right = 0,len(records)-1
        while left<right:
            mid = left+(right-left)//2
            if mid == records[mid]:
                left = mid+1
            else:
                right = mid
        return left+1 if left == records[left] else left