题目重点：利用长连续段必穿过分位下标，先找至多两个候选再二分计频，避免线性多数投票。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 升序整数数组可随机访问，不复制、不重新排序，也不扫描验证有序。
- 返回所有满足严格阈值的不同值并升序排列；最多两个。
- 空数组返回空列表，重复值按出现次数计频，不按不同值数量算n。
解题路线
- 排序保证同值占一个连续块。长度严格大于n/3的块必包含下标floor(n/3)或floor(2n/3)之一，否则只能落在两点分隔出的三个间隙中，任何间隙都不足以容纳这么长的块。
- 读取这两个位置作候选并去重。无需从头扫描找run，也无需Boyer–Moore，它虽O(1)空间但仍要O(n)时间且不利用题目已给的有序性。
- 对每个候选x，lower_bound找首个≥x，upper_bound找首个>x，二者差是精确频次。必须确认频次>floor(n/3)，单纯读取分位值不证明它达到阈值。
- 为什么至多两个？三个不同值若都>n/3，总频次会>n，矛盾。这个上界只约束结果数量，不能说明分位上的所有候选都有效。
- 当n=1或2时，floor(n/3)=0，任何出现值都满足；候选位置可能重合，set去重后仍正确。n可整除3时恰好n/3次应被排除。
- 推广>n/k可取k−1个分位候选、每项二分计数。k固定时O(k log n)；k若随n增长，不可继续宣称整体对n是O(log n)。链表不能常量时间随机取中点，也不满足这里的复杂度假设。
手动走一遍
[1,1,1,2,2,2,3]，n=7，候选下标2和4读到1/2，频次各3，3>7/3，返回[1,2]。[1,1,2,2,3,3]中两候选各2次，恰好n/3，结果空。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Input must already be sorted ascending; do not scan to validate that contract."""
from bisect import bisect_left, bisect_right
def more_than_third(values):
n = len(values)
if not n:
return []
candidates = {values[n // 3], values[(2 * n) // 3]}
return sorted(x for x in candidates
if bisect_right(values, x) - bisect_left(values, x) > n // 3)
复杂度
固定至多两个候选，四次二分，时间O(log n)、额外空间O(1)，输出最多2项。排序与有序性验证不包含在算法内；若输入未经排序，则不能同时获得该保证。
易错点与追问
容易失分的边界
- 超过误写成大于等于。
- 分位候选未经计数直接返回。
- 先排序导致时间O(n log n)。
- 每次二分都复制切片。
继续深挖
- 推广到>n/k如何取候选？
- 数组分布式分片时如何查边界？
- 如果是未排序数组怎么用多数投票？
- 只需判断某值过阈值可少做哪些步骤？
