题解 | #最小的K个数#

时间复杂度O(nlogn)很容易联想到快速排序，结合题目暗示的顺序无关可以进一步优化快排变成半边快排。

首先，简单说一下快排的中心思想，为后续解释做准备。快排的基础是递归，每次递归都会有一个中间值，保证中间值左边的数小于中间值，右边的数大于中间值；然后进行递归，以中间值为分界线对左边数组进行快排，再对右边数组进行快排。

通常一层快排结束后，需要对两边分别进行迭代快排。 但如果只需找最小的K个数，就可以在快排基础上进一步优化：

1、如果中间值位置index恰好等于K-1，那么不必再进行进一步排序，左边的K个数字即是答案（这K个并不一定有序）；

2、如果中间值小于K-1，那么左边这K个数字必定在答案里，只需对中间值右边部分进行迭代快排；

3、如果中间值大于K-1，那么右边这N-K个必定不是答案，只需对中间值左边部分进行迭代快排。

快排的写法因人而异，该思路最大的亮点是半边快排。

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        halfQuickSort(input, 0, input.length-1, k);
        for(int i=0;i<k;i++){
            res.add(input[i]);
        }
        return res;
    }
    
    private static void halfQuickSort(int[] arr, int l, int r, int k){
        if(l>=r) return;
        int i=l, j=r, base= arr[l], tmp;
        while(i<j){
            while (i<j && arr[j]>=base){
                j--;
            }
            while (i<j && arr[i]<=base){
                i++;
            }
            if(i<j){
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        arr[l] = arr[i];
        arr[i] = base;
        if(i==k-1){
            return;
        }else if(i<k-1){
            halfQuickSort(arr, i+1, r, k);
        }else{
            halfQuickSort(arr, l, i-1, k);
        }
    }
}