题解 | #最小的K个数#

思路：

题目的主要信息：

• 对于一个给定无序数组，返回最小的k个元素
• k和数组有特殊情况需要单独讨论，且数组最大10000

方法一：堆排序
具体做法：
使用Java自带的PriorityQueue模拟一个大顶堆，堆的大小限定在最大k：遍历数组，前k个元素直接入堆，后续元素如果比堆顶元素大，则弹出堆顶，再入堆。
最后将所有堆中的元素加入到ArrayList即可返回。

import java.util.ArrayList;
import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (k == 0 || input.length == 0) {
            return res;
        }
        // 大顶堆
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: input) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }
        // 返回堆中的元素
        for(int num: pq) {
            res.add(num);
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：，n个元素，每次维护堆需要
• 空间复杂度：，堆空间最大为k

方法二：直接计数法
具体做法：
因为数据量是限定好的，不超过10000，所以我们可以用大小为10001的数组记录0-10000这些数字在数组中出现的次数，然后遍历计数数组counter，取前面k个存在的数字，如果某个数字出现多次，也需要让它在结果中多次出现，并使k相应往前。

import java.util.ArrayList;
import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (k == 0 || input.length == 0) {
            return res;
        }
        // 统计每个数字出现的次数
        int[] counter = new int[10001];
        for (int num: input) {
            counter[num]++;
        }
        // 根据counter数组从头找出k个数作为返回结果
        for (int num = 0; num < counter.length; num++) {
            while (counter[num]-- > 0 && res.size() < k) {
                res.add(num);
            }
            if (res.size() == k) {
                break;
            }
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：，两次遍历都是单循环
• 空间复杂度：，辅助数组记录每个数组出现的次数