LeetCode 1287：有序数组中超过25%的元素如何用二分查找优化

刷题刷多了会发现一个规律LeetCode 里有些 Easy 题比 Medium 更值得停下来多想两步。1287 就是很典型的一道。题面很简短——在一个有序数组中找到那个出现次数超过 25% 的元素标签也很友好但如果你只是写一个Counter(arr)然后遍历那等于完全没吃到“有序数组”这个红利。这篇我就拿 LeetCode 1287 当例子把从O(n)到O(log n)的完整思考过程写一遍顺便聊聊“耗时 100%”这种提交记录到底是怎么回事。适合刚开始刷二分、想快速秒掉同类 Easy 题或者准备在周赛里减少低级失误的人。1. 题目拆解超过 25% 到底意味着什么1.1 三个容易被忽略的信息先看题目本身的三个关键点。第一数组是有序的。LeetCode 原题里的描述是 sorted array也就是非递减排列。这意味着同一个数值的所有出现位置一定是连续的一段不会出现 1, 2, 1, 2 这种交错情况。这个“连续性”是整个题目的命门后面所有优化的出发点都在这。第二要求是more than 25%不是 more than or equal to。也就是说如果数组长度是 8某个数出现了 2 次那它恰好占 25%不满足条件。这里必须严格大于。第三题目保证答案存在。这一点容易被忽略但它决定了我们可以在算法里大胆地“找到第一个满足条件就返回”。如果没有这个保证最后必须处理找不到的情况。用一句话总结在一个连续值块天然有序的数组里找出哪一个连续区间的长度严格超过数组长度的四分之一。1.2 数学上怎么处理“四分之一”在写代码时不要直接去算n * 0.25。虽然数学上没错但浮点数比较没必要而且容易让读代码的人分心。更干净的做法是span n // 4然后判断某个值的出现次数cnt span即可。这里有个小证明值得想清楚如果cnt n / 4因为cnt是整数它必然至少是n // 4 1。反过来只要cnt n // 4由于n / 4不会超过n // 4 1所以cnt n // 4也一定能推出cnt n / 4。两种判断是等价的而且用整数除法完全避开了浮点误差。另外答案一定唯一。两个不同的元素不可能都出现超过 25%否则它们的总出现次数会超过 50%和数组总长度矛盾。所以返回值不需要做任何去重或二次确认。2. 第一版解法利用有序数组做一次区间跨度判断2.1 先用哈希统计能过但这不是面试官想要的如果完全无视“有序”这个条件最直接的做法是哈希统计from collections import Counter class Solution: def findSpecialInteger(self, arr: List[int]) - int: n len(arr) for x, cnt in Counter(arr).items(): if cnt n // 4: return x return -1这个写法在 LeetCode 上也能 AC时间复杂度O(n)空间复杂度O(n)。但它有一个明显的问题它没有利用数组有序也没有利用“超过 25%”这个比例本身的结构特征。面试里如果只写这一版面试官大概率会追问一句数组有序能带来什么优化所以哈希统计可以作为最基础的思考起点但不要停在原地。2.2 五行的 span 写法窗口长度超过四分之一时必然撞上同一个值既然数组有序同值元素连续出现那我们可以换个角度去看设span n // 4。如果某个数出现次数超过span那它的连续区间长度至少是span 1。在这个区间里一定能找到两个下标i和i span它们指向的元素是同一个数。反过来想如果整个数组里根本不存在任何arr[i] arr[i span]那说明任意一个连续相同值块的长度都不超过span这和题目矛盾。代码可以写成这样class Solution: def findSpecialInteger(self, arr: List[int]) - int: n len(arr) span n // 4 for i in range(n - span): if arr[i] arr[i span]: return arr[i] return -1为什么range(n - span)而不是range(n)因为我们要访问arr[i span]i最大只能取到n - span - 1否则下标越界。这个写法的正确性还有一个更直观的解释arr[i] arr[i span]意味着从i到i span这连续span 1个位置全部是同一个数。而span 1正是“超过四分之一”所需的最小出现次数所以只要找到这一对相等的元素答案就是它。这版的时间复杂度是O(n)空间复杂度O(1)代码比哈希统计短且在竞赛里很好用。但 1287 这道题既然点名了 sorted array最优解显然不止O(n)。3. 二分查找版为什么答案只会藏在三个四等分点里3.1 核心观察把数组切成四段目标区间必然跨过某条分界线这是整道题最精彩的一步。把数组按下标大致切成四段分界线取在n // 4 n // 2 3 * n // 4举个例子n 9时这三个位置是2, 4, 6。数组被分成四段长度大约是2, 2, 2, 3。现在假设目标元素x的出现区间是[L, R]区间长度大于n / 4。如果这个连续区间完整地落在这四段中的某一段内部那它的长度就不可能超过那一段的长度也就是不可能超过大约n / 4。因此只要它长度真的超过n / 4它就必然会跨过至少一条分界线。所以三个分界点上的值必然覆盖了目标候选值。这就是二分查找版本的依据我们根本不需要扫描整个数组只需要检查三个位置上的数再用二分确认它们的出现次数即可。很多人会下意识问为什么不是检查arr[0]或者arr[n - 1]因为它们不是四段之间的分界线而是数组的两端。目标区间如果坐落在开头或结尾它也一定会跨过第一条或最后一条分界线。3.2 用 lower_bound / upper_bound 把候选值的区间拉出来既然候选值只有三个接下来的问题就变成在有序数组中如何快速统计一个值出现了多少次标准做法是用两次二分bisect_left/lower_bound找到第一个不小于目标值的位置。bisect_right/upper_bound找到第一个大于目标值的位置。两次二分的结果之差就是目标值在有序数组中的出现次数。Python 代码from bisect import bisect_left, bisect_right from typing import List class Solution: def findSpecialInteger(self, arr: List[int]) - int: n len(arr) if n 0: return -1 last_candidate None for p in (n // 4, n // 2, 3 * n // 4): cand arr[p] if cand last_candidate: continue left bisect_left(arr, cand) right bisect_right(arr, cand) if right - left n // 4: return cand last_candidate cand return -1C 版本class Solution { public: int findSpecialInteger(vectorint arr) { int n arr.size(); if (n 0) return -1; int prev -1; // LeetCode 原题值域非负可以用 -1 做哨兵 for (int p : {n / 4, n / 2, 3 * n / 4}) { int x arr[p]; if (x prev) continue; auto left lower_bound(arr.begin(), arr.end(), x); auto right upper_bound(arr.begin(), arr.end(), x); if (right - left n / 4) return x; prev x; } return -1; } };这里加了一个last_candidate的小优化。当数组里大量重复元素导致三个候选位上是同一个值时可以跳过后面的重复二分。不加也完全没问题因为最多只会多做几次O(log n)的二分但加了之后代码逻辑更清晰。复杂度方面每个候选值做两次二分一次是O(log n)三个候选值就是常数次二分所以总复杂度是O(log n)空间O(1)。这才是这道题在“有序数组”这个前提下真正想考察的东西。4. 提交记录里的“耗时 100%”复杂度与真实体感4.1 LeetCode 的百分比怎么看标题里的“耗时 100”我理解成 LeetCode 提交记录里常见的Runtime: 100%也就是运行速度超过了一批最近的提交。用 C 提交上面的二分版本时我确实见过类似的百分比。但这里必须说一句LeetCode 的百分比不是严格的性能测试它受服务器负载、测试数据量、甚至同一份代码反复提交的波动影响。今天显示 100%明天可能变成 80%这不代表你的算法退步了。真正值得关注的是复杂度本身。在这个题上O(log n)的二分版本理论上一定优于O(n)的扫描版本。随着数组长度变大二分版本的优势会越来越明显。LeetCode 原题数据量不算大所以O(n)的 span 写法也能轻松通过但这不代表“有序”这个条件不值得利用。4.2 三种解法横向对比在实际面试或竞赛里最好能在脑中像下面这样对比解法时间复杂度空间复杂度核心优势哈希统计O(n)O(n)对数组是否有序没有要求span 区间判断O(n)O(1)代码短利用有序不易写错四分位点 二分O(log n)O(1)有序数组场景下的最优解面试时我建议按这个顺序回答先提哈希统计说明它能解决问题但没有利用有序再提 span 写法展示自己对连续区间的理解最后给二分版本强调复杂度提升到O(log n)。这样一套下来面试官能看到你的思考是有层次的。4.3 为什么“只查三个点”就已经足够有朋友第一次看到二分版本时会担心万一答案区间正好没有完全覆盖分界点只是擦边呢答案是不会。因为答案区间的长度严格大于数组长度的四分之一。把它放到按四等分划分的数组里一个长度超过四分之一总长的连续区间不可能被限制在任意一个四等分的段内部。它要么跨过第一、第二条分界线要么跨过第二、第三条分界线要么跨过第一、第三条分界线。不管是哪一种至少有一个分界点落在区间内部。这个论证不需要依赖数组的具体数值只依赖“有序数组里相同值连续”这个性质。5. 最容易翻车的边界索引、除法和二分习惯5.1 五个常见的坑这类题写起来不难但边界条件很容易翻车。我整理了自己踩过和帮别人看过的几个典型问题。第一个是n // 4和n / 4的混用。Python 3 里/是浮点除法如果拿去当索引直接用类型直接报错C 和 Java 里整数除法会自动截断通常没问题但可读性不如显式除以 4。建议统一用整数除法表达“四分之一”。第二个是 span 写法的range边界。很多人会写成for i in range(n - span 1)最后访问arr[i span]时越界。正确范围是range(n - span)因为i span的最大合法值是n - 1。第三个是“恰好 25%”的情况。比如n 8某个数出现2次它正好是 25%。这时候不能用。代码里判断cnt n // 4也就是2 2结果为false能正确排除。第四个是题目没有保证答案存在的情况。如果是自己做扩展题或者面试官临时改条件最后没找到答案时必须返回-1或题目要求的哨兵值。LeetCode 原题有保证但写防御性代码没坏处。第五个是二分时的上下界选择。bisect_left和bisect_right/lower_bound和upper_bound不要用混。用bisect_left当右边界会把目标值本身排除一部分得到错误计数。最稳妥的记忆方式是左边用 lower右边用 upper区间是左闭右开。5.2 候选人重复时的处理如果数组里大量重复元素比如所有元素都是同一个值那么三个分位点上的候选值也完全相同。此时连续做三次二分是重复劳动。加一个last_candidate跳过即可。需要注意 C 里如果用-1当哨兵而题目值域可能包含负数哨兵方法就不安全。LeetCode 原题arr[i]是非负整数所以没问题如果自己扩展题目更稳妥的做法是直接不跳过或者用一个bool标记是否已经检查过当前候选值。这个细节不算复杂但能在提交记录里省掉几次没必要的二分也算一个小优化。6. 从 1287 延伸出去的三个同类思路6.1 推广到“超过 1/k”1287 的套路可以推广如果有序数组里存在一个出现次数超过n / k的元素那只需要检查arr[n // k] arr[2 * n // k] ... arr[(k - 1) * n // k]一共k - 1个位置。道理和四等分时完全一样长度超过n / k的连续区间一定跨过按k等分后的某条分界线。比如超过 50%就只需检查arr[n // 2]这其实就是大多数场景下的“有序数组多数元素”问题。超过 20%就检查从n // 5到4 * n // 5的四个位置。这个推广比单纯背模板有用得多。6.2 无序数组怎么办如果去掉“有序”这个条件二分就不能用了。最简单的方法是哈希统计时间复杂度O(n)空间O(n)。如果空间有限制可以换用 Boyer-Moore 投票法的推广版本对于超过1/(m1)的元素维护m个候选值和对应计数器最后再验证。比如超过 25%可以维护 3 个候选值。但那个写法代码量更大笔试时我通常还是优先哈希除非题目明确限制了额外空间。6.3 二分边界训练的好素材1287 并不涉及高深算法但它把两种最基础的二分场景——找左边界和找右边界——结合在了一起。如果你每次做“查找第一个大于等于目标值的位置”这类题还要现场推半天边界那 1287 值得多写两遍。我自己练题时会把它和另一道题放在一起LeetCode 1150检查一个数是否在有序数组中占多数。1150 更像是一个“给定 target验证它是否超过一半”的问题1287 则是“自动找出满足条件的值”。两道题互补性很强刷完之后对lower_bound和upper_bound的理解会明显更扎实。最后分享一个我自己的习惯做这类带有序数组的题目先别急着写代码在纸上画一条数轴把数组四等分的点标出来想明白答案为什么一定在这些点附近出现。这一步想通了代码反而是三分钟的事。