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

约 5 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 腾讯 阿里
标签
数组

题目描述

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

image-20260928224121133

题意分析

数组按非递减顺序排列，且恰好有一种值出现次数严格超过总长度的四分之一，要求找出这个值。

有序性保证相同值连续出现，因此高频值对应一段足够长的连续区间。可以先用几个固定位置找到候选，再通过二分计算候选的真实频次。

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

核心思路

[!blue]

令 q = floor(n / 4)，严格超过四分之一等价于至少出现 q + 1 次。选取下标 n / 4、n / 2、3 * n / 4 处的三个值，整数除法均向下取整。

这三个采样位置把未采样的部分分成至多四段，每段长度都不超过 q。若高频值的连续段避开全部采样位置，就只能落在某个这样的空隙中，不可能达到 q + 1 个位置。因此答案必然在三个候选之中。

采样只能保证答案不会遗漏，不能保证每个候选都达标。对候选 num，二分第一个不小于它的位置 left，再二分第一个大于它的位置 right，所有等于它的元素恰好占据 [left, right)，频次就是 right - left。

两次二分都用 [0, n) 作为初始查找范围，右边界可以最终返回 n。区别只在保留左半边的条件：找下界用 arr[mid] >= num，找上界用 arr[mid] > num。用频次严格大于 n / 4 验证，不需要浮点运算。

解题步骤

  1. 根据数组长度取出三个四分位位置的值。
  2. 对每个候选分别调用 lowerBound 和 upperBound，得到完整出现区间。
  3. 若边界差严格大于 n / 4，返回该候选；题目保证答案存在，因此必能找到。

短数组中的采样下标可能重合，不影响正确性；候选始终只有三个，重复验证仍是常数次二分。单元素数组也能直接通过频次判断。

代码实现

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;

        // 高频值的连续段必覆盖至少一个四分位采样点。
        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)

    // 高频值的连续段必覆盖至少一个四分位采样点。
    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+1))$，固定三个候选各两次二分。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 采样负责缩小候选，不能跳过频次验证。
  • 上边界是最后一次出现的下一位，可能等于数组长度。

易错点总结

[!yellow]

  • 只取中点可能错过靠边的高频值。
  • 验证改成大于等于，会接受刚好四分之一。
  • 把三个采样下标先统一整除再乘，会改变覆盖空隙的保证。

相似题目

题目 难度 关联与区别
229. 多数元素 II 中等 都先利用频次阈值证明候选个数上界，再验证真实频次；本题从有序数组分位点取候选，该题用扩展投票维护至多两个候选。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/61576801
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！