给定一个有序数组，统计指定元素出现的次数？｜腾讯 C/C++面经解析

60 秒回答模板

可以这样回答：有序数组统计 target 出现次数，最稳的方法是两次二分：lower_bound 找第一个大于等于 target 的位置，upper_bound 找第一个大于 target 的位置，次数等于 upper-lower。 lower_bound 的不变量是左侧都小于 target，右侧候选都大于等于 target；upper_bound 的不变量是左侧都小于等于 target，右侧候选都大于 target。最后要判断 lower 是否越界或 nums[lower] 是否等于 target。线性扫描 O(n) 简单，二分 O(log n) 更适合大数组。若数组无序，必须先排序或用哈希计数，问题条件会改变复杂度。要处理空数组、不存在、全重复、target 在首尾、单元素和 mid 溢出。闭区间和左闭右开写法不要混用。验证时重点看：用 []、[1]、[1,1,1]、目标不存在、目标在边界和重复段在中间测试。

考点 考点边界

主线 核心机制

易错点 只写普通二分找到一个位置，没找左右边界。

深入解析

考点边界

这题必须围绕“有序数组统计元素次数”本身回答，不能套相邻大类模板。先给定义或目标，再展开机制、边界、取舍和验证抓手。回答时要主动点出题面关键词对应的对象、输入输出和约束条件，避免把具体问题讲成宽泛复习提纲。本题对应“有序数组统计元素次数”，核心前提是：有序数组统计 target 出现次数，最稳的方法是两次二分：lower_bound 找第一个大于等于 target 的位置，upper_bound 找第一个大于 target 的位置，次数等于 upper-lower。

核心机制

lower_bound 的不变量是左侧都小于 target，右侧候选都大于等于 target；upper_bound 的不变量是左侧都小于等于 target，右侧候选都大于 target。最后要判断 lower 是否越界或 nums[lower] 是否等于 target。关键证据要落到状态转移、不变量、边界用例、复杂度来源，这样才能说明机制为什么能支撑题目结论。如果继续展开，要说清状态定义、不变量、边界更新、终止条件和复杂度来源，并用反例说明为什么相邻做法不成立。

关键取舍

线性扫描 O(n) 简单，二分 O(log n) 更适合大数组。若数组无序，必须先排序或用哈希计数，问题条件会改变复杂度。因此要用输入规模、额外空间、最坏复杂度和边界用例来决定方案，而不是只背一个平均复杂度。这些取舍决定了方案在不同输入规模、延迟、内存、并发、泛化或一致性要求下是否仍然成立。

边界风险

要处理空数组、不存在、全重复、target 在首尾、单元素和 mid 溢出。闭区间和左闭右开写法不要混用。排查时优先用空输入、重复值、极端有序数据、溢出、内存上限和复杂度退化样例验证。需要特别关注极端输入、数据分布变化、资源不足、并发竞争或观测口径错误带来的退化。修复时要用最小反例复现错误，再检查边界条件、循环不变量、数据结构选择和复杂度退化点。

验证抓手

验证时要覆盖空输入、单元素、重复元素、边界溢出、极端有序或逆序数据，并明确时间复杂度和空间复杂度。能说出为什么这个复杂度成立，比只写伪代码更可靠。针对本题，最有价值的验证信号是：用 []、[1]、[1,1,1]、目标不存在、目标在边界和重复段在中间测试。把验证抓手说出来，可以让答案从知识点延伸到算法正确性、复杂度和边界用例验证。

易错点

只写普通二分找到一个位置，没找左右边界。
没有处理 target 不存在、空数组、全重复和边界位置。
把相邻概念混用，没有明确说明这道题真正考察的边界。
没有给出验证方式，导致答案听起来完整但无法判断是否真的生效。

面试官追问

为什么不是找到一个 target 后向两边扩？

最坏情况下重复元素很多，向两边扩会退化到 O(n)，两次边界二分始终是 O(log n)。回答时还要补充适用前提、失败场景和验证信号，避免只给一个孤立结论。

lower_bound 和 upper_bound 的返回值如何转成次数？

如果 lower 指向 target，则次数是 upper-lower；如果 lower 越界或不是 target，次数为 0。

“给定一个有序数组统计指定元素出现的次数”继续追问时最该补哪条边界？

应该围绕“有序数组统计元素次数”补适用前提、失败场景和验证证据。先说明哪些条件下这个机制成立，再说明哪些输入规模、并发状态、数据分布或资源限制会让答案需要调整。

“给定一个有序数组统计指定元素出现的次数”怎样回答才不是只背概念？

看它能否把“有序数组统计元素次数”的机制链路、关键取舍和可观测信号连起来。回答时应落到具体状态变化、数据路径、复杂度、指标或排查工具，而不是只复述定义。

“给定一个有序数组统计指定元素出现的次数”怎么判断算法选型？

先看是否有最优子结构、单调性、局部选择是否会影响全局最优，以及数据结构能否降低查找或更新成本。动态规划、贪心、二分、哈希、堆和树结构分别对应不同的不变量。

给定一个有序数组，统计指定元素出现的次数？