剑指 offer 笔记 29 | 最小的 K 个数

题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

题目描述
可用快排思想，改变原数组，我们先数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。

如果这个选中的数字的下标刚好是k，我们就得到了k个小的数字，这些数字在k的左边，并且没有经过排序，但是都比k小。

如果它的下标大于 k，我们可以接着在它的左边部分的数组中查找。

如果它的下标小于 k，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        // 由于本题需要返回ArrayList<Integer>，所以新建之
        ArrayList<Integer> list = new ArrayList<>();
        // 若输入数组长度小于k。直接返回数空的ArrayList
        if(input.length < k){
            return list;
        }

        findKMin(input,0,input.length-1,k);
        for(int i = 0; i < k; i++){
            list.add(input[i]);
        }
        return list;
    }

    private void findKMin(int[] a, int start, int end, int k){
        if(start < end){
            int pos = partition(a, start, end);
            if(pos == k-1){
                return ;
            }else if(pos < k-1){
                findKMin(a,pos+1,end,k);
            }else{
                findKMin(a,start,pos-1,k);
            }
        }
    }

    // 快排中的每次排序实现（挖坑填数法），返回的是交换后start位置（快排一次后的中轴点，中轴点左边全是小于它的，右边都是大于它的）
    public int partition(int[] a, int start, int end){
        int pivot = a[start];
        while(start < end){
            while(start < end && a[end] >= pivot){end--;};
            a[start] = a[end];
            while(start < end && a[start] <= pivot){start++;};
            a[end] = a[start];
        }
        a[start] = pivot;
        return start;
    }
}

参考文献：https://cloud.tencent.com/developer/article/1421609