40-最小的k个数

题目描述

https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof

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

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

思路1: 排序，输出最小的K个数

直接排序将所有的数字都排序了，效率较差，冒泡法是 O(n^2) 快速排序也是 O(nlogn)

实现代码

csharp

public class Solution {
    // 基本思路： 排序，输出最小的K个
    public int[] GetLeastNumbers(int[] arr, int k) {
        if(arr.Length == 0 || k == 0){
            return new int[0];
        }
        // 排序
        for(int i = 0; i < arr.Length -1; i++){
            for(int j = i + 1; j < arr.Length; j++){
                if(arr[i] > arr[j]){
                    //swap
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        // 输出
        int[] newArr = new int[k];
        for(int i=0; i < k; i++){
            newArr[i] = arr[i];
        }
        return newArr;
    }
}

思路2：大根堆

大根堆，也叫优先队列，在 C++ / Java 中有默认实现，即加入队列的元素是按照顺序排列的首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。

java

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        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) {
            vec[i] = queue.poll();
        }
        return vec;
    }
}

思路3：快排思路 Partition

我们可以使用快速排序的思路对数组进行排序，因为题目是需要找到最小的k个数，所以大于k的数字我们不需要排序。只需要对小于k的数字进行排序，当分区等于k的时候，等于找到了答案。

TODO 这个测试用例会超时：[0,0,1,2,4,2,2,3,1,4] ， 8 需要有空研究下。

csharp

public class Solution {
    public int[] GetLeastNumbers(int[] arr, int k) {
        //快速排序
        quickSort(arr,0,arr.Length-1,k);
        //输出结果
        int[] result = new int[k];
        for(int i=0; i<k; i++){
            result[i] = arr[i];
        }
        return result;
    }

    private void quickSort(int[] arr, int start, int end, int k){
        int zoneIndex = partition(arr,start,end);
        // if(zoneIndex == k-1){ //正好排序到，结束排序
        //     return;
        // }
        if(zoneIndex > start){
            quickSort(arr,start, zoneIndex - 1,k);
        }
        if(zoneIndex < end ){ //在k之内的就排序
            quickSort(arr,zoneIndex + 1, end,k);
        }
    }

    private int partition(int[] arr, int start, int end){
        if(start == end){
            return start;
        }
        //随机选择一个数作为基准数
        Random random = new Random();
        int n = random.Next(start, end);
        int pivot = arr[n];
        swap(arr,n,end); //交换到末尾
        int zoneIndex = start-1;
        for(int i=start; i<=end; i++){
            if(arr[i] <= pivot){
                zoneIndex++;
                if(i > zoneIndex){
                    swap(arr,i,zoneIndex);
                }
            }
        }
        return zoneIndex;
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j]=temp;
    }
}

40-最小的k个数 #

题目描述 #

思路1: 排序，输出最小的K个数 #

实现代码 #

思路2： 大根堆 #

思路3： 快排思路 Partition #