剑指offer040找出最小的K个数

Problem:

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

Intuition:

最小的k个数的问题用最大堆来处理，每次最大堆都把较大的数赶出去，留下来自然就是最小的k个数。想象一个场景，一个桶里有100个石头，要挑出里面最小的十个石头，我们怎么挑？把大的90个石头从桶里拿出来剩下的就是最小的十个石头了，那么挑出较大的90个石头需要的工具就是最大堆。

Solution:

public class CodingInterview_040 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
        if (k > nums.length || k <= 0)
            return new ArrayList<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int num : nums) {
            maxHeap.add(num);
            if (maxHeap.size() > k)
                maxHeap.poll();
        }
        return new ArrayList<>(maxHeap);
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        maxHeap.add(3);




        maxHeap.add(1);
        maxHeap.add(2);
        System.out.println(maxHeap.poll());
        System.out.println(maxHeap.poll());
        System.out.println(maxHeap.poll());
        //3 2 1
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(2);
        System.out.println(minHeap.poll());
        System.out.println(minHeap.poll());
        System.out.println(minHeap.poll());
        //1 2 3
    }
}