时间戳

首页 > 解决方案 > 多数元素数组 Java O(nlogn)

java - 多数元素数组 Java O(nlogn)

问题描述

大小为 n 的数组中的多数元素是出现超过 n/2 次的元素。我必须编写一个返回多数元素的函数（如果有，则返回-1），它必须是 O(nlogn)。这就是我得到的：

public class MyMajority implements Majority {
    public int findMajority(Sequence numbers) {
      if (numbers.size()==0) { 
            return -1;
        }
        
        return major(numbers,0,numbers.size()-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);
        int right_count = getFrequency(numbers, right_major);
  
        return left_count > numbers.size() / 2 ? left_major :
                (right_count > numbers.size() / 2 ? right_major : -1);
    }
    
    public int getFrequency(Sequence numbers, int major) {
        int count = 0;
        for(int i=0; i<numbers.size(); i++){
            if(numbers.get(i)==major){
                count++;
                if(count> numbers.size()/2){
                    break;
                }
            }
        }
        return count;
    }

但是，如果我运行代码，一些测试用例会说你的算法太慢了。但我很确定这是 O(nlogn) 我错过了什么吗？因为我使用分治法和循环遍历数组所以 T(n)=2T(n/2)+O(n)=O(nlogn)

标签： javaalgorithmtime-complexity

解决方案

也许您可以尝试这种方法，应该是O(nlogn)：

这很简单sort，找到大多数项目。由于要求表明存在always多数数，因此这里没有考虑边缘情况。

public class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len/2];
    }
}

推荐阅读