剑指offer 29.最小的K个数(优先队列解决法)

时间限制：1秒 空间限制：32768K 本题知识点： 数组

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

思路:
我考虑用最大堆来实现(java自带默认最大堆)可以全部入堆,再出k个元素,即可,但这样会浪费空间,就不符合最小堆动态排序这种特点

import java.util.ArrayList;
import java.util.PriorityQueue;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
         ArrayList<Integer> res = new ArrayList();
        if(k > input.length) {
            return res;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < input.length; i++) {
            pq.add(input[i]);
        }
        for (int i = 0; i < k; i++) {
            Integer remove = pq.remove();
            res.add(remove);
        }
        return res;
    }
}

所用时间和空间:

第二种方法是,先入堆k个数(这次需要最大堆,因为要取出堆顶最大的和接下来的数进行比较),然后后面的数依次与堆顶元素比较,如果比堆顶小,就把堆顶元素给移除,把小的元素放进去就好,最后依次取出堆顶放入list集合返回即可,what?这是最大堆,返回的不是从大到小的顺序吗?错!本题没有要求返回的数据是从小到大排好序的,只是要求返回最小的k个数即可.这种方法节省了空间,保证空间的稳定,但是牺牲的是一部分时间.

import java.util.ArrayList;
import java.util.PriorityQueue;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList();
        if(k > input.length || k == 0) {
            return res;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a,b) -> b - a // 默认就是它,可以不要
        );
        for (int i = 0; i < input.length; i++) {
            if(pq.size() < k) {
                pq.add(input[i]);
                System.out.println(pq.peek());
            } else {
                if (input[i] < pq.peek()) {
                    pq.poll();
                    pq.add(input[i]);
                }
            }
        }
        while (!pq.isEmpty()) {
            Integer remove = pq.remove();
            res.add(remove);
        }
        return res;
    }
}

内存和耗时:

什么鬼,内存和时间更长了?应该是数据太少了,数据多了,就体现出了这样的好处!空间会大大节省.