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

TopN问题: 在一堆数里面寻找N个最值。

排序

将数全排序，找到前N个，复杂度为nlogn，但是如果数据量大，达到10G，那内存就炸了。

TreeSet：

利用TreeSet自动排序的，代码如下，复杂度应该是nlogn。treeset的大小始终控制在K以下，适合大量数据。

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        if(k>input.length) return new ArrayList<Integer>();
        TreeSet<Integer> set = new TreeSet<>();
        for (int i : input) {
            set.add(i);
            if(set.size()>k) set.remove(set.last());
        }
        return new ArrayList<Integer>(set);
    }
}

最小堆、最大堆：

TreeSet和最大最小堆孰优孰劣，涉及到了堆的调整和TreeSet内部的调整。我还没想明白。

image.png

https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf