📃 题目描述

题目链接：剑指 Offer 40. 最小的k个数 (opens new window)

🔔 解题思路

最大堆

和 剑指 Offer II 060. 出现频率最高的 k 个数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 思路一样，本题用一个大小为 k 的大根堆，如果堆的元素个数 < k，那么直接插入，如果堆的元素个数 == k，并且当前遍历到的数 > 大根堆的堆顶，那么这个数一定不是最小的 k 的数

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
            (o1, o2) -> o2 - o1
        );

        for (int num : arr) {
            if (maxHeap.size() < k) {
                maxHeap.offer(num);
            }
            // maxHeap.size() >= k
            else {
                if (num >= maxHeap.peek()) {
                    continue;
                }

                maxHeap.poll();
                maxHeap.offer(num);
            }
        }

        int[] res = new int[k];
        int i = 0;
        while (!maxHeap.isEmpty()) {
            res[i ++] = maxHeap.poll();
        }

        return res;
    }
}

快速排序

快速排序 partition 的作用，返回 pivot 的最终位置，并且，左边的数都小于 arr[pivot]，右边的数都大于 arr[pivot]

这道题不需要对最小的 k 个数进行排序，如果 pivot 的下标正好就是 k - 1，那么 arr[0, pivot] 就是 最小的 k 个数

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        select(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr, k);
        // return Arrays.copyOfRange(arr, 0, k);
    }

    private void select(int[] arr, int left, int right, int k) {
        if (left > right) {
            return ;
        }

        int pivot = partition(arr, left, right);
        // 找到 pivot == k -1, 则停止排序
        if (pivot == k - 1) {
            return ;
        }
        else if (pivot < k - 1) {
            select(arr, pivot + 1, right, k);
        }
        else {
            select(arr, left, pivot - 1, k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int index = left + new Random().nextInt(right - left + 1);
        swap(arr, index, left);

        int pivot = left;

        while (left < right) {
            while (left < right && arr[right] >= arr[pivot]) {
                right --;
            }
            while (left < right && arr[left] <= arr[pivot]) {
                left ++;
            }

            if (left < right) {
                swap(arr, left, right);
            }
        }

        swap(arr, left, pivot);

        return left;
    }

    private void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：