目录
力扣LCR 173. 点名
难度 简单
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records
。假定仅有一位同学缺席,请返回他的学号。
示例 1:
输入: records = [0,1,2,3,5] 输出: 4
示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7
提示:
1 <= records.length <= 10000
class Solution {
public:
int takeAttendance(vector<int>& records) {
}
};
解析代码
此题就是以前写过的剑指Offer中数组消失的数字,以前用的位运算的解法解的,此题解法有哈希,遍历,位运算,数学求和,时间都是O(N),二分的解法是O(logN)。
二段性就是找的元素的值肯定不等于数组下标,求左端点的套路:
class Solution {
public:
int takeAttendance(vector<int>& records) {
// 解法有哈希,遍历,位运算,数学求和,时间都是O(N),二分的解法是O(logN)
// 此题二段性就是找的元素的值肯定不等于数组下标,求左端点的套路
int left = 0, right = records.size() - 1;
if(records[right] == right)
{
return right + 1;
}
while(left < right)
{
int mid = left + (right - left) / 2;
if(records[mid] == mid)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return records[left] - 1;
}
};