[剑指offer][Java]最小的k个数

题目

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

程序核心思想

这个题目很简单，只需要一个能够帮你排序的数据结构就可以了，我这边选择的是优先队列，优先队列的底层是堆结构，所以，如果不想使用这种现成的结构，可以自己实现一个最小堆，然后弹出堆顶，然后将堆底的元素放入堆顶，然后heapify，然后继续弹出堆顶，直到弹出前k个堆顶即可。

Tips

要问清楚，如果给定数组只有5个数，结果要弹出最小的10个数的时候怎么办？是返回null，还是返回[]，还是返回5个，剩下的没有就算了？？

问清楚。

代码

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

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        ArrayList<Integer> arr = new ArrayList<Integer>();

        if(input == null || k == 0 || k > input.length)    return arr;
        
        for(int i = 0; i < input.length; i++){
            pq.offer(input[i]);
        }
        
        for(int i = 0; i < k; i++){
            arr.add(pq.poll());
        }

        return arr;
    }
}