Top面试题-最小的k个数

该题来自【牛客网 - 题库 - 在线编程】

题目描述

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组

示例

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

解析

这道题刚来过来最容易想到的就是讲数组排好序，然后直接取前 k 个数就可以，但是这种方式并不是最优解，所以需要想想别的方式来解决这道题。

解法一：快速排序法

快速排序想必大家都不陌生，先选取一个基准点，然后使用双指针的方式将比基准点小的数移到左边，大的数移到右边。其实这道题就可以利用快排的思维来解决这道题：

先选取一个基准点；
将小于基准点的数移到左边，大于的移到右边；
判断基准点和 k - 1 的关系，如果等于：那么直接返回基准点以及基准点之前的数据；如果小于：需要对基准点右侧重新进行快排；如果大于：对基准点左侧进行快排。一直到找到 基准点 等于 k - 1 的时候。

AC 代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        if (k == 0 || input.length == 0) {
            return new ArrayList();
        }
         if (k > input.length) {

            return new ArrayList<Integer>();
        }
        // 找到基准点等于 k - 1 的时候
        return quickSearch(input, 0, input.length - 1, k - 1);
    }

    private ArrayList<Integer> quickSearch(int[] input, int lo, int hi, int k) {
        // 每次快排后的基准点的位置
        int j = partition(input, lo, hi);
        // 如果等于 k 也就是实际的 k-1，说明找到了最终的位置
        if (j == k) {
            // 将基准点及以前的数据返回
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            for (int i = 0; i < j + 1; i ++) {
                arrayList.add(input[i]);
            }

            return arrayList;
        }
        // 如果基准点不等于 k - 1， 则判断是对左侧还是右侧做快排逻辑
        return j > k? quickSearch(input, lo, j - 1, k): quickSearch(input, j + 1, hi, k);
    }

    // 将比基准点小的放到左边，大的放到右边
    private int partition(int[] input, int lo, int hi) {
        // 基准点 point
        int point = input[lo];
        // 左右指针
        int i = lo, j = hi + 1;
        while (true) {
            // 如果小于基准点，左指针向右移动
            while (++i <= hi && input[i] < point);
            // 如果大于基准点，右指针向左移动
            while (--j >= lo && input[j] > point);
            if (i >= j) {
                break;
            }
            // 当左右指针遇到大于等于基准值时，做交换
            int t = input[j];
            input[j] = input[i];
            input[i] = t;
        }
        input[lo] = input[j];
        input[j] = point;
        return j;
    }
}

时间复杂度：平均时间复杂度为O(n),,最坏时间复杂度为O(n^2)
空间复杂度：O(1)

解法二：大根堆法

其实这道题不只是使用上面的快排方法，咱们不是要最小的 k 个数嘛，是不是只要维护一个容量为 k，并且存储的是数组中最小的数，然后将这些都取出来就是答案了呗。而这个数据结构用 大根堆 来做最适合不过了。
简单说一下大根堆：其实就是维护一个数据结构，堆顶一直都是这个数据中的最大值。
为啥用大根堆而不用 小根堆？因为咱们要不断去将这些数据中的最大值替换成比其小的值，以此来达到维护最小数据的目的。说的差不多了，接下来上代码。

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        // 判空处理
        if (input == null || input.length < 1 || k < 1) {
            return new ArrayList();
        } 
        // 如果数组长度小于k，那么直接全部返回就可以了
        if (input.length <= k) {
            return Arrays.asList(input);
        }
        // 结果集
        ArrayList<Integer> result = new ArrayList<Integer>();
        // 创建的大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        // 先填充大小为 k 的大根堆
        for (int i = 0; i < k; i ++) {
            queue.offer(arr[i]);
        }
        // 遍历剩下的数据
        for (int i = k; i < arr.length; i ++) {
            // 如果大根堆 堆顶 大于 下一个元素，就将堆顶的元素移除，将小于堆顶的元素放入
            if (queue.peek() > arr[i]) {
                // 移除
                queue.poll();
                // 放入
                queue.offer(arr[i]);
            }
        }
        // 组装结果集
        for (int i = 0; i < k; i ++) {
            result.add(queue.poll());
        }

        return result;
    }
}

时间复杂度：O(nlogk)，其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 nn 个数都会插入，所以一共需要O(nlogk) 的时间复杂度。

空间复杂度：O(k),大根堆的的容量。