面试题40. 最小的k个数(简单)

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

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof

思路1：

堆排序，一个容量为k的堆（求最小的k个数就用大顶堆，反之用小顶堆），如果堆容量没到k，遍历值就直接进入，如果满了，则比较堆顶元素，如果堆顶元素大于要进来的元素，则堆顶poll，元素进堆，否则元素不进堆

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0 || arr.length==0)
            return new int[0];
        //大根堆
        Queue<Integer> queue = new PriorityQueue<Integer>((v1,v2)->v2-v1);
    
        for(int ar:arr){
            if(queue.size()<k)
                queue.offer(ar);
            else if(queue.peek()>ar){
                queue.poll();
                queue.offer(ar);//最后剩下的k个就是要求的
            }
        }

        //输出，数组
        int[] out = new int[queue.size()];
        int i =0;
        for(int que:queue){
            out[i++]=que;
        }
        //这种遍历总报错
        // for(int i=0;i<=queue.size();++i){
        //     out[i]= queue.poll();
        // }
        return out;
    }
}