思路:

题目的主要信息:

  • 对于一个给定无序数组,返回最小的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;
    }
}

复杂度分析:

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