Java实现：以O(k log n)时间查找有序数组中出现超n/k次的整数

对于有序数组，若存在某个数出现次数超过n/k，那么它必然会覆盖至少一个间隔为n/k的位置（比如索引0, n/k, 2n/k...）——因为如果一个数的连续长度超过n/k，不可能避开所有这些间隔点。基于这个特性，我们只需检查这些候选位置的元素，用二分查找快速计算每个候选的出现次数，即可在O(k log n)时间内找到结果。

import java.util.Arrays;

public class MajorityElementOverK {
    public static int findElementOverNK(int[] arr, int k) {
        int n = arr.length;
        // 边界值判断：数组为空、k不满足0<k<n的情况直接返回-1
        if (n == 0 || k <= 1 || k >= n) {
            return -1;
        }
        int step = n / k;
        // 遍历所有候选间隔点
        for (int i = 0; i < k; i++) {
            int idx = i * step;
            if (idx >= n) {
                break;
            }
            int candidate = arr[idx];
            // 二分查找候选元素的左边界（第一个等于该元素的索引）
            int leftBound = findLeftBound(arr, candidate);
            // 二分查找候选元素的右边界（第一个大于该元素的索引）
            int rightBound = findRightBound(arr, candidate);
            // 计算出现次数
            int count = rightBound - leftBound;
            if (count > n / k) {
                return candidate;
            }
        }
        // 没有符合条件的元素
        return -1;
    }

    private static int findLeftBound(int[] arr, int target) {
        int left = 0, 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 static int findRightBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        // 测试用例1：存在符合条件的元素
        int[] arr1 = {1, 2, 2, 2, 3, 4};
        System.out.println(findElementOverNK(arr1, 3)); // 输出2

        // 测试用例2：不存在符合条件的元素
        int[] arr2 = {1, 2, 3, 4, 5};
        System.out.println(findElementOverNK(arr2, 2)); // 输出-1

        // 测试用例3：多个候选元素，返回第一个符合条件的
        int[] arr3 = {1,1,1,2,2,3,3,3};
        System.out.println(findElementOverNK(arr3, 3)); // 输出1
    }
}

• 时间复杂度：循环最多执行k次，每次循环包含两次二分查找（时间复杂度O(log n)），总时间复杂度为O(k log n)，完全符合要求。
• 空间复杂度：仅使用常数级额外空间，为O(1)。

内容的提问来源于stack exchange，提问作者user9068199