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;elseright = mid;}return left;}
};