最小的K个数

题目：

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

方法一：时间复杂度为 O(n) 的算法，只有当我们可以修改输入的数组时可用

利用快速排序划分的思想，每一次划分就会有一个数字位于以数组从小到达排列的的最终位置index；
位于index左边的数字都小于index对应的值，右边都大于index指向的值；
所以，当index > k-1时，表示k个最小数字一定在index的左边，此时，只需要对index的左边进行划分即可；
当index < k - 1时，说明index及index左边数字还没能满足k个数字，需要继续对k右边进行划分；

代码如下：

public static int[] getLeastNumbers(int[] input, int k) {

    int[] output = new int[k];

    if (input == null || k <= 0 || input.length <= 0) {
        return output;
    }

    int start = 0;
    int length = input.length;
    int end = length - 1;
    int index = partition(input, length, start, end);

    while (index != k - 1) {
        if (index > k - 1) {
            end = index - 1;
            index = partition(input, length, start, end);
        } else {
            start = index + 1;
            index = partition(input, length, start, end);
        }
    }

    for (int i = 0; i < k; i++) {
        output[i] = input[i];
    }

    return output;
}

//划分操作
private static int partition(int[] data, int length, int start, int end) {
    if (data == null || length <= 0 || start < 0 || end > length) {
        throw new RuntimeException("invalid arguments");
    }

    int index = new Random().nextInt(end - start) + start;
    swap(data, index, end);
    int small = start - 1;
    for (index = start; index < end; index++) {
        if (data[index] < data[end]) {
            ++small;
            if (small != index) {
                swap(data, index, small);
            }
        }
    }

    ++small;
    swap(data, small, end);
    return small;
}

private static void swap(int[] data, int x, int y) {
    int temp = data[x];
    data[x] = data[y];
    data[y] = temp;
}

解法二：时间复杂度为 O(nlogK) 的算法，特别适合处理海量数据

• 可以先创建一个大小为k的数据容器来存储最小的k个数字，从输入的n个整数中一个一个读入放入该容器中，如果容器中的数字少于k个，按题目要求直接返回空；

• 如果容器中已有k个数字，而数组中还有值未加入，此时就不能直接插入了，而需要替换容器中的值。按以下步骤进行插入：

  • 先找到容器中的最大值；
  • 将待查入值和最大值比较，如果待查入值大于容器中的最大值，则直接舍弃这个待查入值即可；如果待查入值小于容器中的最大值，则用这个待查入值替换掉容器中的最大值；

  重复上述步骤，容器中最后就是整个数组的最小k个数字。

  对于这个容器的实现，我们可以使用最大堆的数据结构，最大堆中，根节点的值大于它的子树中的任意节点值。Java中的 TreeSet 类实现了红黑树的功能，它底层是通过 TreeMap 实现的，TreeSet 中的数据会按照插入数据自动升序排列（按自然顺序）。因此我们直接将数据依次放入到 TreeSet 中，数组就会自动排序。
  代码如下：

public static ArrayList<Integer> GetLeastNumbers_Solution3(int [] input, int k) {
    if(input == null)
        return null;
    ArrayList<Integer> list = new ArrayList<Integer>(k);
    if(k > input.length)
        return list;
    TreeSet<Integer> tree = new TreeSet<Integer>();
    for(int i = 0 ; i < input.length; i++){
        tree.add(input[i]);
    }
    int i = 0;
    for(Integer elem : tree){
        if(i >= k)
            break;
        list.add(elem);
        i++;
    }
    return list;
}

时间复杂度为O(nlogn)，优点：

1. 不会改变原来数组；
2. 这种思想，适合处理海量数据，特别是n大k小的情况。在处理海量数据的时候，受内存限制，数据可能不能一次全部读入内存，此时用这种方式也很好处理，只要想每次读入一些数据，与我们的容器中最大值比较，看是否需要进行替换操作。

缺点就是：
TreeSet不允许重复数据，因为TreeSet的底层是TreeMap实现，是将TreeSet添加的内容作为TreeMap的key值来存储，也就不能存在重复数据。由于这种限制，这就对我们的输入数组有要求，但我们可以通过自己实现最大堆或优化TreeSet来实现兼容存在重复数字的情况。

————————————————
版权声明：本文为CSDN博主「山代王」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/shakespeare001/article/details/51280814