题解 | #最小的K个数#

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){
            //如果选择的基点 位置在 k 左边
            if(index > k - 1){
                end = index -1;
                index = parition(input, start, end);
            }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[left +index] = data[left];
        data[left] = value;
        int j = left;
         
        for(int i = left +1;i<= right;i++ ){
            if(data[i] < value){
                data[j] = data[i];
                j++;
               data[i] = data[j];
            }
        }
        data[j] = value;
         
        return j;
    }
    
}