題目

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;}
};