用快速排序解决「不要求有序」的最小 k 个树

题目链接-来源：力扣（LeetCode）

输入整数数组 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]

思路：

找 最小/最大 的 k 个数，习惯性地可以想到 最大堆 / 最小堆 来解决。复杂度为 O(nlogk)。
当然，注意到本题的条件，不要求按顺序输出结果，那么我们可以用一种更聪明的办法，那就是借助「快速排序」。
快速排序的每一轮排序当中，我们会确定一个 pivot ，在这个 pivot 左侧的元素都比它要小，右侧的元素都比它要大。那么我们只要在某轮排序中，发现 pivot 的左侧元素刚好为 k 个，那么这 k 个元素就是我们所要寻找的结果。
我们快速排序的目标不再是真的「排序」，而是想办法让 pivot 左侧恰好有 k 个元素。
细节：快排的划分策略，我们采用双指针法，分别从数组开头和结尾查看元素，当前指针元素大于 pivot 且后指针元素小于 pivot 时，交换两个元素，直到两指针相遇时停止。
时间复杂度：O(n²)最坏情况。绝大多数情况为O(logn)，快排特性。
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int left = 0, right = arr.length - 1;
        for (int len = partition(arr, left, right); len != k;) {
            if (len < k) {
                len = partition(arr, len + 1, right);
            } else {
                len = partition(arr, left, len - 1);
            }
        }
        int[] res = new int[k];
        System.arraycopy(arr, 0, res, 0, k);
        return res;
    }
    
    private int partition(int[] arr, int left, int right) {
        if (left >= right) {
            return left;
        }
        int pivot = arr[left];
        int i = left, j = right;
        while (i < j) {
            while (arr[j] >= pivot && i < j) {
                j--;
            }
            while (arr[i] <= pivot && i < j) {
                i++;
            }
            swap(arr, i, j);
        }
        if (arr[left] > arr[i]) {
            swap(arr, left, i);
        }
        
        return i;
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}