题解 | #最小的K个数#

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        if(input == null || input.length == 0) {
            return ans;
        }
        if(k < 1 || k > input.length) {
            return ans;
        }
        findKthLest(input, k - 1);
        for (int i = 0; i < k; i++)
            ans.add(input[i]);
        return ans;
    }
    public void findKthLest(int[] nums, int k) {
        int l = 0, h = nums.length - 1;
        while(l < h) {
            int j = partition(nums, l, h);
            if(j == k) {
                break;
            } else if(j > k) {
                h = j - 1;
            } else {
                l = j + 1;
            }
        }
    }
    public int partition(int[] nums, int l, int h) {
        int p = nums[l];     /* 切分元素 */
        int i = l, j = h + 1;
        while (true) {
            while (i != h && nums[++i] < p) ;
            while (j != l && nums[--j] > p) ;
            if (i >= j)
                break;
            swap(nums, i, j);
        }
        swap(nums, l, j);
        return j;
    }
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}