欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer:最小的K个数

程序员文章站 2022-03-01 12:54:26
...

试题:

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

代码:

使用有序结构存储这k个数就可以了

import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList res = new ArrayList<Integer>();
        int len = input.length;
        if(len==0 || k>len || k==0) return res;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2.compareTo(o1);
            }
        });
        
        for(int num : input){
            if(maxHeap.size()!=k){
                maxHeap.offer(num);
            }else if(maxHeap.peek() > num){
                maxHeap.poll();
                maxHeap.offer(num);
            }
        }
        for(Integer num: maxHeap) res.add(num);
        return res;
    }
}