题解 | #最小的K个数#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>(k);
        if (input.length < k) {
            return list;
        }
        quickSort(input, 0, input.length - 1);
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }


        return list;
    }



    public static void quickSort(int[] arr, int low, int high) {
        //log.info("arr: {},low:{},high:{}", arr, low, high);
        if (low < high) {
            // 找到划分点
            int pivotIndex = index(arr, low, high);
            //log.info("pivotIndex: {},arr:{}", pivotIndex, arr);

            // 递归地对左右两部分进行快速排序
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }



    private static int index(int[] array, int low, int high) {
        int idx = array[high];
        int i = (low - 1);
        for (int j = low ; j < high ; j++) {
            if (idx >= array[j]) {
                i++;
                // 移动数据，小于基准值的放在最左面
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        // 本次移动之后，将基准值放入左面 i 之后
        int temp = array[i + 1] ;
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

}


排序后截取数据