LCR 173：在点名（二分查找） —— 题解

欢迎阅读 欢迎来到「点名」题解之旅本文将带你从点名时发现学号缺了一个这一直观场景出发深入理解二段性二分的巧妙运用并掌握如何比较元素与下标是否相等来定位缺失的学号。在开始之前建议你先了解题目背景这是 LCR 173 题给定递增数组records其元素本应为0 ~ n的连续整数但缺失了一个数字找出它。本质上缺失位置之前满足records[i] i之后满足records[i] ! i问题转化为二分找到第一个下标与值不相等的位置。明确学习目标掌握下标-值比较二分理解缺失在中间与缺失在末尾两种情形的区分并熟练处理单元素数组等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如records [0,1,2,3,5]输出4records [0,1,2,3,4]输出5。本文将从问题转化、下标比较、区间收缩、结果校验到代码实现层层递进。即使你对二段性二分还不熟悉我们也会从谁和座号对不上谁就是缺席者这一直觉出发让你轻松抓住核心思想——下标值相等为左段不等即缺失。现在让我们一起二分点名找出那个缺勤的学号吧 一.题目LCR 173. 点名 - 力扣LeetCode​二.做题思路一、问题分析前置分析题目要求在递增数组records中找出缺失的那个整数元素本应为0 ~ n连续缺失一个。关键约束数组严格递增元素范围[0, n1]内缺一个缺失数字可能在中间也可能在末尾。核心思路利用二段性——缺失位置前满足records[i] i缺失位置后满足records[i] i 1整体右移一位二分找第一个records[i] ! i的位置。二、算法策略下标-值比较二分核心步骤初始化区间n records.size() - 1数组最后一个下标、left 0、right n在[0, n]上二分。二分收敛while (left right)mid下取整left (right - left) / 2。下标比较mid records[mid]→ 前mid1个元素全部正确缺失在右半left mid 1mid ! records[mid]→ 缺失在左半含 midright mid。结果校验收敛后若records[left] left说明缺失的是末尾数字n 1返回left 1否则返回left。示例执行过程records [0,1,2,3,5]缺失 4阶段leftrightmidrecords[mid] vs mid操作结果①0422 2左段正确收缩左侧left3②3433 3左段正确收缩左侧left4收敛44—records[4]5 ! 4返回 44三、正确性说明简单版本二段性成立数组只缺一个数字缺失位置前所有元素满足records[i] i之后所有元素满足records[i] i整体右移两种状态只切换一次判据mid records[mid]恰好识别分界不会误判。收缩方向正确相等说明左段完好缺失在右半可丢弃左段不等说明缺失在左半含 mid保留 mid 向左收敛。区间单调收敛到第一个不等位置不漏解。末尾缺失校验完备若全部相等缺失的是最后一位n1二分会收敛到right n此时records[left] left恒成立返回left 1恰好是缺失值覆盖末尾情形。终止性left mid 1与right mid下取整保证mid right均严格缩小不会死循环。四、实现细节边界防护初始化n records.size() - 1数组最后一个下标非元素个数、left 0、right n。边界防护size 1时如[0]right 0循环不进入records[0] 0→ 返回 1records[left]访问安全left ≤ n ≤ size-1缺失在末尾时靠校验分支兜底。复杂度时间 O(log n)每次排除一半空间 O(1)仅常数个变量。关键判断if (mid records[mid]) left mid 1; else right mid;二段性收敛、if (records[left] left) return left 1;末尾缺失校验。五、返回值目标映射返回left或left 1缺失的数字对应题目返回缺席的学号。三.代码class Solution { public: int takeAttendance(vectorint records) { int n records.size() - 1; // 数组最后一个下标搜索区间右端点 int left 0; int right n; // 1. 二段性二分比较元素与下标找“第一个 records[i] ! i”的位置 while (left right) { int mid left (right - left) / 2; // mid 下取整配合 right mid if (mid records[mid]) { left mid 1; // 前 mid1 个元素全部正确缺失在右半 } else { right mid; // 已出现错位缺失在左半含 mid } } // 2. 结果校验区分“缺失在中间”与“缺失在末尾” if (records[left] left) { return left 1; // 全部元素都与下标相等缺失的是末尾数字 } return left; // 第一个错位下标即缺失数字 } };四、易错点分析难点1n records.size() - 1的含义极易混淆int n records.size() - 1; // 注意这是“最后一个下标”不是元素个数 int right n;这里的n是数组最后一个下标搜索右端点而缺失数字的取值范围是[0, size]。若误把n当成元素个数records.size()right会越界一位收敛后records[left]访问越界UB。理解搜索区间是下标域 [0, size-1]缺失值域是 [0, size]是正确写对边界的前提。难点2判据mid records[mid]的语义是左段完好if (mid records[mid]) left mid 1; // 跳过 midrecords[mid] mid说明前 mid1 个元素全部与下标相等数组递增且只缺一个错位只会在之后发生因此缺失必在[mid1, right]left mid 1跳过 mid 是安全的。若误写成left mid当所有元素都正确时left卡在size-1无法前进死循环left right恒成立但 left 不再增大实际 leftmid 且 midleft 时区间不缩小。难点3else 分支right mid保留 mid 的原因else right mid; // records[mid] ! mid缺失在 [left, mid] 内records[mid] ! mid时mid 可能是第一个错位位置即缺失值也可能在其右侧但缺失一定不在 mid 之后递增性mid 之后的值都 ≥ records[mid]1 mid1错位更明显但第一个错位在 mid 或更左。保留 mid 向左收敛不会漏掉第一个错位点。难点4末尾缺失必须靠records[left] left兜底if (records[left] left) return left 1; // 全部相等 → 缺失的是 n1若缺失的是最后一个数字如[0,1,2,3,4]缺 5数组内所有元素都与下标相等二分一路left mid 1收敛到left size-1。此时若直接return left会误返回 size-1必须校验records[left] left后返回left 1——这个校验分支是末尾缺失情形的唯一出口漏掉即错。五、流程图 闭幕 恭喜你完成了「点名」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题通过比较records[mid]与下标mid来判断缺失位置。为什么这种比较能揭示缺失信息其背后的“元素与下标对应关系”在有序无重复场景下具有什么特性循环结束后代码额外校验if (records[left] left) return left 1;。这个分支处理的是什么情况如果不加这个校验直接返回left在什么场景下会出错时间复杂度 O(log n)如果改用异或运算或求和公式时间复杂度也是 O(n)相比二分哪种方案更优为什么本题要求用二分延伸挑战如果数组长度不固定且缺失的数字可能出现在任意位置包括开头和末尾当前的二分框架是否依然适用如果数组中的数字不是从 0 开始例如从 1 到 n缺失一个你如何修改比较条件来适配这种偏移如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案比较records[mid]与mid的有效性因为数组是 0~n 范围内的不重复升序排列若左侧元素全部正确则records[i] i对i k恒成立一旦出现错位缺失数字就在该位置此后所有元素都比下标大 1形成“左段正确、右段错位”的二段性。当mid ! records[mid]时说明mid已经位于错位段缺失一定在mid或其左侧因此right mid向左收缩不会丢失缺失数字。异或或求和 O(n) 比 O(log n) 慢但更简单本题要求二分是为了训练二段性思维且 O(log n) 更高效。延伸挑战答案挑战1若缺失位置任意开头或末尾只要数组仍是 0~n 的不重复升序排列当前二分完全适用因为二段性依然存在开头缺失则第一个元素就不等于0mid比较立即触发错位分支。挑战2若数组从 1 开始即应有records[i] i 1只需将比较条件改为mid 1 records[mid]其余收敛逻辑不变即可适配任意偏移。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨