LeetCode - LCR 173. 点名

题目

LCR 173. 点名 - 力扣（LeetCode）

思路

首先对数组进行排序，使学号按顺序排列

在排序后的数组中，如果没有缺失的学号，那么每个元素应该等于其索引值

使用二分查找找到第一个不等于其索引的元素位置：

• 如果 records[mid] == mid，说明缺失的数字在右半部分

• 如果 records[mid] > mid，说明缺失的数字在左半部分（包括mid）

循环结束时，left 指向的是第一个不等于其索引的位置，即缺失的学号

时间复杂度：O(n log n)，主要是排序的时间复杂度

空间复杂度：O(1)，只使用常数额外空间

读者可能出现的错误写法 

class Solution {
public: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;}}return right;}
};

边界情况处理：

你的代码没有处理缺失的是最后一个数字（即n-1）的情况。循环结束后，如果 records[right] == right，说明缺失的是最后一个数字。

正确写法

class Solution {
public: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;}}if(records[left] == right){return right+1;}return right;}
};