LeetCode 1287. 有序数组中出现次数超过25%的元素

2026-04-01 HGNULB 约 12 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 1287. 有序数组中出现次数超过25%的元素

题意分析

给一个非递减的整数数组 arr，题目保证其中恰好存在一个元素，它的出现次数严格超过数组长度的 25%，要求把这个元素找出来并返回。

两个条件必须先咬清楚。第一是「有序」——相同的值一定挤在一起形成一个连续区间，于是「某个值出现了多少次」等价于「它所在区间的右端点减左端点」，统计问题被转化成了边界定位问题。第二是「保证存在且唯一」——不需要处理找不到答案的情况，也不需要在多个候选之间比较大小，找到第一个满足条件的就能直接返回。

「超过 25%」的门槛要按严格不等号理解：设 n = arr.length，答案的出现次数 cnt 满足 cnt > n / 4。这里 n / 4 用整数除法即可——因为 cnt 和 n 都是整数，cnt * 4 > n 与 cnt > n / 4（向下取整）在整数域上是等价的。

约束里 $1 \le n \le 10^4$，值域 $0 \le arr[i] \le 10^5$，规模本身很小，$O(n)$ 的线性扫描随手就能过。真正的信号藏在「有序」这两个字上：题目特意把数组排好序，又特意选了 25% 这个能被 4 整除的比例，这是在暗示存在一个比线性更快的做法，也是面试里会被追问的那一层。

边界：n = 1 时唯一的元素出现 1 次，而 n / 4 = 0，1 > 0 成立，它就是答案；n = 4 时门槛是 1，需要至少出现 2 次；数组可能全是同一个值；答案可能贴在数组的最左端或最右端。

解法：四分位采样 + 二分边界

核心思路

暴力做法是从左到右扫一遍，用一个变量记录当前连续段的起点，段结束时算出长度并和 n / 4 比较。这是 $O(n)$ 时间、$O(1)$ 空间，完全正确，也是很多人写出的第一版。

瓶颈在于：它把每一个元素都读了一遍，而绝大多数元素属于短段，根本不可能是答案。有序性提供的信息被浪费了——我们明明可以直接跳到数组的某个位置去看那里是什么值，而不必逐个走过去。

关键观察：把数组按下标切成四段，分界点在 n/4、n/2、3n/4。如果某个值占据的连续区间长度严格大于 n/4，那么这个区间的长度就超过了任意一段的长度，它不可能被塞进任何一段的内部而不碰到分界点——一个长度大于 n/4 的连续区间，必然覆盖 n/4、n/2、3n/4 这三个下标中的至少一个。

换个更直观的说法：想象把三根桩子钉在 n/4、n/2、3n/4 上，相邻桩子之间的间距恰好是 n/4（整除误差不影响结论），一根长度超过 n/4 的木条无论怎么摆，都至少压住一根桩子。

这条性质把候选集从 n 个元素压缩到了 3 个：arr[n/4]、arr[n/2]、arr[3*n/4]。剩下的工作只是逐个验证候选值的出现次数是否真的超过 n/4。

验证出现次数就回到了有序数组的经典操作：对候选值 num，用 lowerBound(arr, num) 求出第一个 ≥ num 的下标 left，用 upperBound(arr, num) 求出第一个 > num 的下标 right，那么 num 的出现次数就是 right - left。两个二分的不变量都写成左闭右开区间 [left, right)：循环开始前答案一定落在这个区间里，每轮把区间缩小一半而不丢掉答案，循环在 left == right 时终止，此时区间收缩为空，left 就是要找的分界下标。

lowerBound 和 upperBound 的唯一差别只在比较符：前者用 arr[mid] >= target 决定收缩右边界，后者用 arr[mid] > target。这一个等号决定了「相等时往左收还是往右收」，从而决定了求到的是区间的开头还是结尾。

因为题目保证答案存在，三个候选里必然有一个通过验证，末尾的 return arr[0] 只是为了让编译器满意的兜底分支，逻辑上不可达。

解题步骤

取三个候选值：arr[n/4]、arr[n/2]、arr[3*n/4]。为什么是这三个而不是 n/4 的所有倍数：门槛是「严格大于 n/4」，区间长度至少 n/4 + 1，跨度已经超过相邻桩子的间距，三根桩子足够拦住它。下标本身不会越界：n ≥ 1 时 3*n/4 ≤ n - 1 恒成立（n = 1,2,3 时 3n/4 分别是 0, 1, 2）。

逐个候选验证：对每个 num，求 left = lowerBound(arr, num) 与 right = upperBound(arr, num)，若 right - left > n / 4 就立即返回 num。用「先算次数再比较」而不是「边二分边计数」，是因为次数这个量本身就是两个边界的差，拆成两次标准二分比写一个变种二分更不容易错。

lowerBound 的写法：left = 0、right = arr.length（不是 length - 1，因为区间左闭右开，right 是一个哨兵位，表示「所有元素都比 target 小」的情况）；循环条件 left < right；mid = left + (right - left) / 2 防止大数相加溢出；arr[mid] >= target 时说明答案在 mid 或更左，收 right = mid（不能写 mid - 1，mid 本身可能就是答案）；否则 left = mid + 1（mid 已被排除，可以跳过）。

upperBound 的写法：结构完全相同，只把判断改成 arr[mid] > target。相等时走 else 分支往右收，于是最终停在最后一个 target 的下一格。

返回：三个候选按顺序试，命中即返；结尾的 return arr[0] 在题目约束下不会被执行到。

以 arr = [1, 2, 2, 6, 6, 6, 6, 7, 10] 走一遍，n = 9，门槛 n / 4 = 2（整除）。

三个采样下标是 9/4 = 2、9/2 = 4、27/4 = 6，对应候选值 arr[2] = 2、arr[4] = 6、arr[6] = 6。

验证候选 2：lowerBound(2) 在 [0, 9) 上二分，mid = 4，arr[4] = 6 >= 2，收成 [0, 4)；mid = 2，arr[2] = 2 >= 2，收成 [0, 2)；mid = 1，arr[1] = 2 >= 2，收成 [0, 1)；mid = 0，arr[0] = 1 < 2，left = 1，区间空，返回 1。upperBound(2) 同理停在 3。出现次数 3 - 1 = 2，2 > 2 不成立，候选作废——注意这里正是严格不等号救了场，写成 >= 就会错误地返回 2。

验证候选 6：lowerBound(6) 返回 3（第一个 6 的位置），upperBound(6) 返回 7（最后一个 6 的下一格）。出现次数 7 - 3 = 4，4 > 2 成立，返回 6。

再看极端用例 arr = [1]：n = 1，门槛 0，三个候选下标都是 0，候选值都是 1；lowerBound(1) = 0、upperBound(1) = 1，次数 1 > 0 成立，返回 1。整个流程不需要为单元素写任何特判。

代码实现

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        // 超过 n/4 的众数一定盖住这三个四分位下标中的至少一个。
        int[] candidates = {arr[n / 4], arr[n / 2], arr[3 * n / 4]};

        for (int num : candidates) {
            int left = lowerBound(arr, num);
            int right = upperBound(arr, num);
            if (right - left > n / 4) {
                return num;
            }
        }

        return arr[0];
    }

    private int lowerBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

func findSpecialInteger(arr []int) int {
    n := len(arr)
    // 超过 n/4 的众数一定盖住这三个四分位下标中的至少一个。
    candidates := []int{arr[n/4], arr[n/2], arr[3*n/4]}

    for _, num := range candidates {
        left := lowerBoundInt(arr, num)
        right := upperBoundInt(arr, num)
        if right-left > n/4 {
            return num
        }
    }

    return arr[0]
}

func lowerBoundInt(arr []int, target int) int {
    left, right := 0, len(arr)
    for left < right {
        mid := left + (right-left)/2
        if arr[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

func upperBoundInt(arr []int, target int) int {
    left, right := 0, len(arr)
    for left < right {
        mid := left + (right-left)/2
        if arr[mid] > target {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

复杂度分析

时间复杂度：$O(\log n)$。候选只有固定的 3 个，与 n 无关；每个候选做两次二分，每次二分把区间对半砍，最多 $O(\log n)$ 轮。常数是 6 次二分，总共约 $6\log n$ 次比较。这比暴力扫描的 $O(n)$ 严格更优，也是这道「简单」题真正的看点。

空间复杂度：$O(1)$。只用了 n、一个长度为 3 的候选数组和二分里的 left、right、mid 几个整型变量，不随输入规模增长，也没有递归栈——两个二分都写成了迭代形式。

关键点总结

有序数组里「统计出现次数」应当条件反射地翻译成「求左右边界之差」，upperBound - lowerBound 是这个转换的标准形式，比自己写循环计数更快也更不易错。

抽屉原理的下标版本：一段长度超过 n/k 的连续区间，必然覆盖把数组等分成 k 份的那些分界下标中的至少一个。这条性质可以直接推广——「超过 n/3」采样 n/3 和 2n/3，「超过 n/2」只需采样 n/2，把候选集从 $O(n)$ 压到 $O(k)$。

左闭右开是二分最省心的区间约定：right 初值取 arr.length 而非 length - 1，收缩时 right = mid 与 left = mid + 1 不对称，终止条件 left < right，返回值 left。这四件事必须成套使用，混搭必然出死循环或差一错误。

lowerBound 与 upperBound 只差一个等号，理解「相等时往哪边收」就理解了整个二分边界家族，不必背四套模板。

严格大于的门槛不能松成大于等于。题目写「超过 25%」，写成 >= 会让恰好占 25% 的元素蒙混过关，这是本题唯一的语义陷阱。

面试视角：先给出 $O(n)$ 的一趟扫描说明自己能正确解题，然后主动指出「数组已经排好序，这个条件还没用上」，再引出四分位采样把复杂度压到 $O(\log n)$。被追问「为什么只需要三个候选」时，用抽屉原理正面证明；被追问「如果改成超过 n/k」时，答「采样 k-1 个分界点，复杂度 $O(k\log n)$」。这一整套推导比答案本身更能体现水平。

易错点总结

错误写法：门槛判断写成 right - left >= n / 4 → 对 [1, 2, 2, 6, 6, 6, 6, 7, 10]，候选 2 的出现次数是 2，2 >= 2 成立，会错误返回 2 而不是 6。

错误写法：候选只取 arr[n/2] 一个 → 对 [1, 1, 1, 2, 3, 4, 5, 6]（n = 8，门槛 2，答案是出现 3 次的 1），arr[4] = 3 只出现 1 次，验证失败后掉进兜底分支，返回值不可靠。

错误写法：二分的 right 初值写成 arr.length - 1 → 对 [1, 1, 1, 1] 求 upperBound(1)，正确答案是 4，但右边界封顶在 3，只能返回 3，算出的次数少 1；数组全是同一个值时必错。

错误写法：lowerBound 里把 right = mid 写成 right = mid - 1 → 会跳过 mid 这个可能正是答案的位置。对 [6, 6, 6] 求 lowerBound(6)，mid = 1 时满足 >= 却把区间收成 [0, 0)，虽然此例侥幸返回 0，但在 [5, 6, 6] 上会漏掉正确边界。

错误写法：upperBound 的判断也写成 >= → 两个函数变成同一个，right - left 恒为 0，任何候选都验证不过，最终永远返回 arr[0]。

错误写法：mid 写成 (left + right) / 2 → 本题 n ≤ 10^4 不会溢出，但这是必须养成的肌肉记忆；一旦二分的是值域（比如 0 到 10^9），left + right 就会越过 int 上界变成负数，arr[mid] 直接抛越界。

错误写法：循环条件写成 left <= right 却仍用 right = mid → 区间语义混搭，left == right 时 mid 恒等于 left，若 arr[mid] >= target 则 right = mid 不变，陷入死循环，直接超时。

错误写法：采样下标写成 arr[3 * (n / 4)] 而不是 arr[3 * n / 4] → 两者在 n 不是 4 的倍数时不同。n = 9 时前者是 arr[6]（巧合相同），n = 6 时前者是 arr[3]、后者是 arr[4]，采样点偏左会让某些靠右的答案漏掉。

错误写法：为了「省事」直接用哈希表统计频次 → 答案对，但完全放弃了有序这个条件，复杂度退回 $O(n)$ 时间加 $O(n)$ 空间，比暴力扫描还差，面试里等于交白卷。

错误写法：忘了 n = 1 会让 n / 4 == 0，于是加一个 if (n < 4) return arr[0]; 的特判 → 特判本身结果碰巧对，但会掩盖主逻辑的边界能力；更糟的变体是写成 if (n < 4) return arr[n / 2];，在 [1, 1, 2] 上返回 1 正确、在 [1, 2, 2] 上返回 2 正确，却在 [1, 2, 3] 这种（题目虽不保证出现的）输入上给出无意义结果，掩盖了真实错误。

相似题目

题目	难度	考察点
169. 多数元素	简单	门槛是超过 `n/2` 且数组无序，靠 Boyer-Moore 投票在 $O(1)$ 空间内一趟求出
229. 多数元素 II	中等	门槛降到 `n/3`，答案最多两个，投票法要同时维护两个候选并做二次校验
34. 在排序数组中查找元素的第一个和最后一个位置	中等	直接考 `lowerBound` 与 `upperBound` 这一对边界二分，本题把它当作子过程调用
剑指 Offer 53 - I. 在排序数组中查找数字 I	简单	求指定值的出现次数，就是本题验证候选那一步单独拿出来出成一道题
540. 有序数组中的单一元素	中等	同样利用有序 + 成对结构，但二分的判定依据是下标奇偶性而非值的比较
35. 搜索插入位置	简单	答案正是 `lowerBound` 的返回值，是理解左闭右开区间语义最干净的入门题
704. 二分查找	简单	只判断存在性，不涉及边界收缩方向，可用来校准 `mid` 计算与循环终止条件
面试题 17.10. 主要元素	简单	与 169 同门槛但不保证答案存在，必须在投票后补一趟校验，考察「保证存在」的价值