题解 | #最小的K个数#TOP46

思路:
1.二分法，得到index,左边的数比index位置数小，右边比它大
2.直到index == k - 1, 选择 0 到 k -1 下标的数就是最小的k个数

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (input == null || input.length == 0 || k <= 0 || input.length < k) {
            return new ArrayList<Integer>();
        }
        //方法一 排序 前面k个数 O(nlogN)-O(n2)
        //方法二 快速排序中 使得左边都小于第K个元素   O(n)

        int start = 0;
        int end = input.length - 1;
        int index = parition(input, start, end);
        while(index != k - 1){
            if(index > k - 1){
                end = index - 1;
            }else {
                start = index + 1;
            }
            index = parition(input, start, end );
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(input[i]);
        }
        return  result;
    }
    private static int parition(int[] data, int left, int right) {
        //随机选择二分法的基准数据
        int index = new Random().nextInt(right - left + 1);
        int value = data[index + left];
        data[index + left] = data[left];
        data[left] = value;
        int j = left;
        
        for(int i = left+1; i <= right ; i++){
            //当前j赋值i,然后下一个数放在i的位置上，j 到 i之间的数是比value大的数
            if(data[i]  < value){
                data[j] = data[i];
                j ++;
                data[i] = data[j];
            }
        }
        data[j] = value;
        return j;
    }

}