首页 > 试题广场 >

有 500W 个无序的数字类型的数据,希望以尽量快的速度找出

[问答题]
有 500W 个无序的数字类型的数据,希望以尽量快的速度找出这 500W 数据中最大的 N(1<N<100)个,请编写段程序实现这个要求。
使用优先队列实现的小根堆来获取最大k数?
import java.util.Comparator;
import java.util.PriorityQueue;
 
public class Test2018_3 {
    public static PriorityQueue<Integer> kmax(int[]arr,int k){
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer integer, Integer t1) {
                return integer-t1;
            }
        });
        for(int i=0;i<arr.length;i++){
            if(priorityQueue.size()<k){
                priorityQueue.offer(arr[i]);
            }else{
                if(arr[i]>priorityQueue.peek()){
                    priorityQueue.poll();
                    priorityQueue.offer(arr[i]);
                }
            }
        }
        return priorityQueue;
    }
 
    public static void main(String[]args){
        int[] arr={1,2,4,3,5,6,7,212,45,67,34,454,65,87,23,76,98};
        PriorityQueue<Integer> priorityQueue=kmax(arr,5);
        while(!priorityQueue.isEmpty()){
            System.out.println(priorityQueue.poll());
        }
    }
}


发表于 2020-02-19 16:24:32 回复(0)