C++ 面试高频考点 LCR 137. 点名 二分查找 题解 每日一题

题目描述

题目链接：LCR 173. 点名

题目表述：

示例 1：
输入：records = [0,1,2,3,5]
输出：4
解释：学号范围为 0~4（共 5 位同学），数组中缺少 4，故返回 4。

示例 2：
输入：records = [0, 1, 2, 3, 4, 5, 6, 8]
输出：7
解释：学号范围为 0~7（共 8 位同学），数组中缺少 7，故返回 7。

提示：

1. 1 <= records.length <= 10000
2. records 是严格升序排列的数组（学号无重复、无乱序）
3. 仅存在一位同学缺席，且缺席学号在 0 ~ records.length 范围内（如 records 长度为 1 时，缺席学号为 0 或 1）

为什么这道题值得你用几分钟的时间弄懂？

这道题的难度标签虽为“简单”，但它的价值远不止“解决一道题”本身——它是一道典型的“一题多解、以题练思维”的优质题目，核心价值体现在三点：

1. 覆盖多类基础算法思想：从暴力遍历的“直观思维”，到高斯求和的“数学思维”，再到哈希表的“映射思维”、位运算的“二进制特性思维”，最后到二分查找的“二段性优化思维”。每一种解法都对应一类核心算法逻辑，能帮你一次性梳理“不同场景下如何选择算法”的思路。

2. 面试高频“开胃题”：面试官常以这类题目作为技术面开场——通过提问“你能想到哪些解法？不同解法的时间/空间复杂度如何？如何从 O(n) 优化到 O(logn)？”，快速判断你的算法基础是否扎实、是否具备“优化意识”。掌握这道题的多种解法，能让你在面试中更从容。

3. 二分查找的“收尾巩固题”：如果你正在系统学习二分查找（比如跟进我的二分系列博客），这道题是绝佳的“收尾练习”——它的“二段性”不依赖“目标值对比”，而是基于“下标与元素的对应关系”，能帮你跳出“二分只能找具体值”的固有认知，彻底理解二分的核心逻辑。

同样我再墨迹一句，因为这是我们算法系列关于二分查找的最后一道题目，我不会着重讨论二分查找的通用细节（如 mid 计算方式、循环终止条件等），如果是第一次接触我的博客的朋友，建议先从这篇博客开始力扣 704.二分查找 基础二分查找，可以进入我的主页这段时间我做的题目都是关于二分查找的，可以从上面的那个博客往后看相信会让你对二分理解的更加深刻；如果是一直跟进的老朋友，直接往下看即可。

可以做出这道题的方法

这道题的解法可按“时间复杂度”分为两类：前4种方法时间复杂度为 O(n)（适合入门理解），第5种方法（二分查找）可优化至 O(logn)（适合进阶优化），具体对比如下表：

解法	核心逻辑	时间复杂度	空间复杂度	适用场景
暴力遍历	遍历数组，对比每个下标与元素值，找到第一个“下标≠元素”的位置	O(n)	O(1)	数组长度较小时（简单直观）
高斯求和	用“0~n-1的总和”减去“数组元素总和”，差值即为缺席学号	O(n)	O(1)	避免遍历判断，依赖数学公式
哈希表	将数组元素存入哈希表，再遍历“0~数组长度”，找未在哈希表中的编号	O(n)	O(n)	需频繁查询元素是否存在时
位运算	利用“xx=0、x0=x”，将“0~n-1”与数组元素异或，结果即为缺席学号	O(n)	O(1)	追求极致空间优化（无额外变量）
二分查找	利用“下标与元素的对应关系”的二段性，快速定位缺席学号	O(logn)	O(1)	数组有序且需高效查询时（最优）

因为这篇博客是以二分为主所以我们先来讨论二分查找的方法如何实现，我会把其他的几种方法在后面有兴趣的朋友可以在看完二分之后去看一看

二分查找

由于题目中明确数组是“严格升序”的，我们可以利用“二段性”将复杂度优化至 O(logn)，这也是这道题的核心价值所在。

二分的依据

这道题是我先入为主的向大家说明了可以用以上的方法，但是我们仍要想明白为什么这道题可以用二分查找来解决，依据是什么？当然一定是这段数组中有二段性我们可以利用。

最开始我想这道题的时候是这样想二段性的，我通过用records[left]或records[right]减去records[mid]与left或者right减去mid来做比较，如果不相等就证明缺失的学生在区间中，反之则不在，但是在处理边界情况的时候我这个通过区间的方法存在的问题太多，属实是简单题复杂做自己折磨自己了

二分查找的核心是“找到一个条件，将数组分为两段，且目标值只在其中一段”。这道题的“二段性”来源于“下标与元素值的对应关系”，具体可拆解为：

• 左段（正常段）：对于任意下标 i，满足 records[i] == i（未出现缺席，学号与下标完全匹配）；
• 右段（异常段）：对于任意下标 i，满足 records[i] > i（出现缺席后，后续所有元素的下标都比学号小1，如 [0,1,2,3,5] 中，5的下标是4，4 < 5）。

而缺席学号就是“左段的最后一个下标 + 1”，也等价于“右段的第一个下标”。如下图，我们要找的目标点也就是下标为7值为8的点：

二分算法的实现

基于上述“二段性”，我们可以通过对比 records[mid] 与 mid 的关系，不断缩小查找范围：

核心判断逻辑
设当前查找区间为 [left, right]，计算中间下标 mid = left + (right - left)/2（避免溢出）：

1. 若 records[mid] == mid：mid 属于“正常段”，右段的第一个下标一定在 mid 右侧，因此缩小左边界：left = mid + 1；
2. 若 records[mid] > mid：mid 属于“异常段”，右段的第一个下标可能是 mid 或在 mid 左侧，因此缩小右边界：right = mid。

边界情况处理
有两种边界情况

• 左边界缺失（如[1]又或是[1,2,3,5]）
• 右边界缺失（[0,1,2,3,4]）

我们的算法目前已经能够处理"左边界缺失"的情况。

不过还有另一种"右边界缺失"的情况需要处理，比如数组[0,1,2,3,4]，这种情况下缺失的最小正整数其实是5，也就是在整个数组的最右边外面。

为什么会出现这种情况呢？因为在我们的算法里，当查找右边界时，有一个left = mid + 1的操作，这个操作会让left指针不断向右移动，最终停在整个数组的最右边位置。

所以我们只需要在算法的最后加一个判断：

• 看看这个最终停在最右边的left指针，它的下标值是否等于数组中对应位置的元素值（也就是检查nums[left] == left是否成立）
• 如果相等，说明数组从0开始一直连续到了最后一位，那缺失的就是下一个数，也就是left + 1
• 如果不相等，那就按照原来的逻辑返回-1就可以了

这样就能同时正确处理左右两种边界缺失的情况了。

二分代码实现（O(logn)）

class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0, right = records.size() - 1;// 二分查找：找到右段的第一个下标while (left < right) {int mid = left + (right - left) / 2; // 避免溢出if (records[mid] == mid) {// mid 在正常段，右段在 mid 右侧left = mid + 1;} else {// mid 在异常段，右段在 mid 左侧或就是 midright = mid;}}// 循环结束后 left == right，判断是否为“无异常段”的情况return records[left] == left ? left + 1 : left;}
};

代码解释

• 循环终止条件：left < right（确保最终 left == right，指向目标位置）；
• 最终判断：records[left] == left 表示数组无异常段（如 [0,1,2,3]），此时缺席学号为 left + 1（4）；否则 left 就是右段第一个下标（即缺席学号）。

其他方法

方法1：暴力遍历（O(n)）

核心思路
由于数组严格升序且学号从0开始，未缺席时，每个下标 i 对应的元素值必为 i。若出现“i ≠ records[i]”，则 i 就是缺席学号；若遍历结束仍全部相等（如 records = [0,1,2,3]），则缺席学号为数组长度（即 4）。

代码实现

class Solution {
public:int takeAttendance(vector<int>& records) {int n = records.size();for (int i = 0; i < n; ++i) {if (records[i] != i) { // 找到第一个下标≠元素的位置，即为缺席学号return i;}}// 遍历结束仍全部相等，缺席学号为数组长度（如 [0,1,2] 缺席 3）return n;}
};

方法2：高斯求和（O(n)）

核心思路

1. 学生总数 total_students = records.size() + 1（因为缺席1人，数组长度比总人数少1）；
2. 用等差数列求和公式计算“0~total_students-1 的总和”：sum_total = total_students * (total_students - 1) / 2；
3. 计算数组 records 的元素总和 sum_records；
4. 缺席学号 = sum_total - sum_records（总学号和减去已到场学号和）。

代码实现

class Solution {
public:int takeAttendance(vector<int>& records) {int n = records.size();int total_students = n + 1;// 计算 0~total_students-1 的总和（等差数列求和）int sum_total = total_students * (total_students - 1) / 2;// 计算数组元素总和int sum_records = 0;for (int num : records) {sum_records += num;}// 差值即为缺席学号return sum_total - sum_records;}
};

方法3：哈希表（O(n)）

核心思路

1. 将数组 records 中的所有元素存入哈希表（unordered_set），利用哈希表“O(1) 查找”的特性；
2. 遍历“0 ~ records.size()”（所有可能的学号），判断每个学号是否在哈希表中，未出现的即为缺席学号。

代码实现

#include <unordered_set>
using namespace std;class Solution {
public:int takeAttendance(vector<int>& records) {unordered_set<int> st(records.begin(), records.end());int n = records.size();// 遍历所有可能的学号（0 ~ n）for (int i = 0; i <= n; ++i) {if (st.find(i) == st.end()) { // 未在哈希表中找到，即为缺席学号return i;}}return -1; // 逻辑上不会走到这里}
};

方法4：位运算（O(n)）

核心思路
利用异或（^）的两个核心性质：

• 性质1：x ^ x = 0（相同数字异或为0，可抵消重复值）；
• 性质2：x ^ 0 = x（数字与0异或仍为自身）。

实现步骤

1. 初始化结果 res = 0；
2. 先将 res 与“0 ~ records.size()”的所有学号异或（覆盖所有可能的学号）；
3. 再将 res 与数组 records 中的所有元素异或（抵消已到场的学号）；
4. 最终 res 即为缺席学号（未被抵消的唯一值）。

代码实现

class Solution {
public:int takeAttendance(vector<int>& records) {int n = records.size();int res = 0;// 第一步：异或所有可能的学号（0 ~ n）for (int i = 0; i <= n; ++i) {res ^= i;}// 第二步：异或数组中的已到场学号（抵消重复值）for (int num : records) {res ^= num;}return res; // 剩余的就是缺席学号}
};

二分查找系列小结

至此，我们的“二分查找系列”博客已全部结束。回顾整个系列，我们从“基础二分查找”到“进阶二分查找”，核心是围绕“如何找到二段性”展开——这也是二分查找的灵魂，就像最开始说的二分查找会了不难难了不会。

总结二分查找的核心要点：

1. 二段性是前提：无论数组是“整体有序”还是“分段有序”，只要能找到一个条件将数组分为“目标在左”和“目标在右”两段，就能用二分；
2. 边界处理是关键：根据“是否包含目标值”决定边界收缩方式（如 left = mid + 1 或 left = mid），避免死循环；
3. 复杂度是优势：二分查找的时间复杂度固定为 O(logn)，在有序数组的查询场景中，是优于 O(n) 解法的“最优选择”。

下题预告

二分查找系列告一段落，接下来我们将进入新的算法模块——“前缀和”。下一篇博客将讲解牛客网的 DP34 【模板】前缀和 题目。

前缀和是“快速计算数组区间和”的核心技巧，广泛应用于数组、矩阵的区间查询问题，也是动态规划、滑动窗口等算法的基础。跟着系列文章一步步学，你对算法的掌握会越来越系统～