LeetCode刷题【面试题 17.14】最小K个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

题解，9月3日的每日一题

看到题目第一反应，找一组无序数字中的最小，或者最大的几个，典型的用堆来解决的问题，不过在写堆之前，可以尝试自己写一个类似的逻辑的代码。

维护一个长度为k的有序数组，遍历原数组，挨个将数组中的值加入到维护的k长度数组中，在加入的时候，判断这个值和数组中已有值的大小关系，将这个值插入到k的对应位置，保持数组k的单调性。如果长度k的数组加入值的时候长度将会超过k，则移除掉末尾的最大值。

class Solution {
    int[] list;
    int listCount = 0;
    public int[] smallestK(int[] arr, int k) {
        if (k == 0){
            return new int[0];
        }
        list = new int[k];
        Arrays.fill(list,Integer.MIN_VALUE);

        for (int i = 0; i < arr.length; i++) {
            if (listCount < list.length){
                //此时list还没满
                listAdd(arr[i]);
            }else{
                listInsert(arr[i]);
            }
        }

        return list;

    }

    public void listAdd( int num ){
        if (listCount == 0){
            list[0] = num;
            listCount++;
            return;
        }
        //比如
        //[1,2,4,5,6]找到4比3大
        //[1,2,3,4,5,6]把4、5、6往后挪移一位在4的位置插入
        for (int i = 0; i < list.length; i++) {
            if (list[i] > num){
                System.arraycopy(list,i,list,i+1,listCount-i);
                list[i] = num;
                listCount++;
                return;
            }
        }
        list[listCount] = num;
        listCount++;
    }

    public void listInsert( int num ){
        for (int i = 0; i < list.length; i++) {
            if (list[i] > num){
                System.arraycopy(list,i,list,i+1,list.length-i-1);
                list[i] = num;
                break;
            }
        }
    }
}

在这个代码中，比如原数组[1,2,4,5,6]，想把[4,5,6]往后移动一位，需要从末位开始往前遍历移动，例如，把6先移动到索引5的位置，再移动5到索引4的位置，再移动3。如果是从前面开始，先移动4，则会覆盖到5的位置，导致后面想移动5的时候，5已经不存在了被4覆盖掉了。这边我原本一开始是这么写的逻辑，不过提交的时候，emmm，超时了…….，这样的有序排列的结果移动复制的方法，可以保证在多出k个的时候能自动将最大值移出数组。

所以大概回顾了下整个的代码逻辑，最耗时的部分好像在这个复制的地方，那么修改一下，使用System.arraycopy这个native方法来代替原来自己写的for循环。确实可以过了。结果如下，在超时的边缘不断疯狂尝试。

解答成功:
执行耗时:1821 ms,击败了5.37% 的Java用户
内存消耗:47.9 MB,击败了55.67% 的Java用户

嗯，想一下哪边能有优化的呢，原来的复制部分的问题用System.arraycopy处理了，接下来看起来应该是在数组内查找的地方可以优化。这里可以改成二分，找到第一个比当前值大的值的索引。

堆实现

这里我们先直接改成堆试试看

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (k == 0){
            return new int[0];
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o));
        for (int j : arr) {
            queue.add(j);
        }
        int[] list = new int[k];
        int count = 0;
        while (!queue.isEmpty() && count <k){
            list[count] = queue.poll();
            count++;
        }
        return list;
    }
}

解答成功:
执行耗时:19 ms,击败了38.21% 的Java用户
内存消耗:46.5 MB,击败了87.38% 的Java用

接下来，另一个思路，先排序，排序后取前面k个结果返回，先撸一版代码，直接先调用API来试试

class Solution2 {
    public int[] smallestK(int[] arr, int k) {
        if (k == 0){
            return new int[0];
        }
        int[] list = new int[k];
        Arrays.sort(arr);
        System.arraycopy(arr,0,list,0,k);
        return list;

    }
}

解答成功:
执行耗时:6 ms,击败了70.64% 的Java用户
内存消耗:48.2 MB,击败了20.73% 的Java用户

emmm这速度可以啊