题解 | 最小的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
        //快速排序的思想
        if (k == 0) return new ArrayList<>();
        int idx = quickSort(input, 0, input.length-1, k);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i<=idx; i++) {
            list.add(input[i]);
        }
        return list;
    }

    private int quickSort(int[] arr, int left, int right, int k) {
        int pivot = partition(arr, left, right);
        if (pivot + 1 == k) {
            return pivot;
        } else if (pivot < k - 1) { //说明在右边
            return quickSort(arr, pivot + 1, right, k);
        } else {
            return quickSort(arr, left, pivot-1, k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int val = arr[left];
        int key = left;
        while (left < right) {
            while (left < right && arr[right] >= val) {
                right--;
            }
            while (left < right && arr[left] <= val) {
                left++;
            }
            if (left < right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }

        if (key != left) {
            int tmp = arr[left];
            arr[left] = arr[key];
            arr[key] = tmp;
        }
        return left;
    }
}