我想在泉州做网站,只知道网站后台怎么做301,网址导航源码,企业自建站案例题目
LCR 173. 点名 - 力扣#xff08;LeetCode#xff09;
思路
首先对数组进行排序#xff0c;使学号按顺序排列
在排序后的数组中#xff0c;如果没有缺失的学号#xff0c;那么每个元素应该等于其索引值
使用二分查找找到第一个不等于其索引的元素位置#xff1…题目
LCR 173. 点名 - 力扣LeetCode
思路
首先对数组进行排序使学号按顺序排列
在排序后的数组中如果没有缺失的学号那么每个元素应该等于其索引值
使用二分查找找到第一个不等于其索引的元素位置
如果 records[mid] mid说明缺失的数字在右半部分
如果 records[mid] mid说明缺失的数字在左半部分包括mid
循环结束时left 指向的是第一个不等于其索引的位置即缺失的学号
时间复杂度O(n log n)主要是排序的时间复杂度
空间复杂度O(1)只使用常数额外空间
读者可能出现的错误写法
class Solution {
public:int takeAttendance(vectorint records) {int left 0;int right records.size()-1;while(left right){int mid left (right - left)/2;if(records[mid] mid){left mid1;}else{right mid;}}return right;}
};
边界情况处理
你的代码没有处理缺失的是最后一个数字即n-1的情况。循环结束后如果 records[right] right说明缺失的是最后一个数字。
正确写法
class Solution {
public:int takeAttendance(vectorint records) {int left 0;int right records.size()-1;while(left right){int mid left (right - left)/2;if(records[mid] mid){left mid1;}else{right mid;}}if(records[left] right){return right1;}return right;}
};
