Java实现O(nlogn)复杂度查找数组多数元素算法超时原因排查

核心问题1：时间复杂度推导错误，实际复杂度为O(n²) #

你推导的T(n)=2T(n/2)+O(n)递推式成立的前提是，合并两个子问题的代价与当前递归区间长度正相关。但你代码中的getFrequency方法每次都会遍历整个数组，而非当前递归的[low, high]区间：

• 分治总共有logn层，第i层会产生2^i个子问题
• 每个子问题都会遍历长度为n的整个数组，单步操作为O(n)
• 总时间复杂度实际为O(n * 2^logn) = O(n²)，数据量稍大就会触发超时

核心问题2：分治逻辑存在语义错误 #

分治的核心逻辑是：先找左右子区间的多数元素（在子区间内出现次数超过子区间长度的1/2），如果两个候选一致则为当前区间的多数元素，否则统计两个候选在当前区间的出现次数，超过当前区间长度1/2的才是当前区间的多数元素，否则返回-1。
你现在的逻辑直接统计候选在全局的出现次数，会导致子区间的返回结果完全不符合分治逻辑的预期，中间递归过程几乎都是无用功。

其他可能的优化点 #

如果Sequence接口的实现是链表而非随机访问数组，get(i)操作的时间复杂度是O(i)而非O(1)，会进一步放大耗时。可以先把Sequence转为数组再处理，或者改用迭代器遍历统计次数。

修复方案 #

1. 修改getFrequency方法，新增low、high参数，仅统计当前区间内的目标元素出现次数
2. 合并左右子问题时，判断候选在当前[low, high]区间的出现次数是否超过(high-low+1)/2，而非全局长度的1/2
3. 递归得到最终候选后，可以再遍历一次全局数组做最终校验，避免边界错误，额外的O(n)遍历不影响整体复杂度
   修复后的核心代码示例：

public class MyMajority implements Majority {
    public int findMajority(Sequence numbers) {
        if (numbers.size()==0) { 
            return -1;
        }
        int candidate = major(numbers,0,numbers.size()-1);
        if(candidate == -1) return -1;
        // 全局校验确保结果正确
        int cnt = getFrequency(numbers, candidate, 0, numbers.size()-1);
        return cnt > numbers.size()/2 ? candidate : -1;
    }
    
    public int major(Sequence numbers, int low, int high) {
        if (low == high){
            return numbers.get(low);  
        } 
        int mid = (high - low) / 2 + low;
        int left_major = major(numbers, low, mid);
        int right_major = major(numbers, mid + 1, high);
        
        if (left_major == right_major){
            return left_major; 
        } 
        // 仅统计当前区间的出现次数
        int left_count = getFrequency(numbers, left_major, low, high);
        int right_count = getFrequency(numbers, right_major, low, high);
        int curLen = high - low + 1;
        return left_count > curLen / 2 ? left_major :
                (right_count > curLen / 2 ? right_major : -1);
    }
    
    public int getFrequency(Sequence numbers, int major, int low, int high) {
        int count = 0;
        for(int i=low; i<=high; i++){
            if(numbers.get(i)==major){
                count++;
            }
        }
        return count;
    }
}

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