题解 | #最小的K个数#

方法一：先排序，在找到前K个

以下用Java实现，用Java自带的数组排序方法进行升序排列，然后保存前K个。因为返回类型定义为ArrayList动态数组，因此需要将前k个依次装入结果数组；如果返回类型直接就是数组，我们可以调用Arrays.copyOf(arr, index)直接得到前k个元素的数组拷贝。

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ret = new  ArrayList<Integer>();
        if (k > input.length){ // 本题说明条件
            return ret; // 空数组
        }
        Arrays.sort(input);
        for (int i = 0; i < k; i++) {
            ret.add(input[i]);
        }
        return ret; 
    }
}

方法二：快排

只需要找到位置在k处的哨兵即可，不需要完全排序

import java.util.ArrayList;

public class Solution{
    private void QuickSort(int[] input, int l, int r, int k){
        if (l >= r) return;
        int key = input[l];
        int i = l,j = r;

        while (i < j) {
            // 从右开始找大的
            while (i < j && input[j] >= key)
                j--;
            input[i] = input[j];
            // 从左开始找小的
            while (i < j && input[i] <= key)
                i++;
            input[j] = input[i];
        }
        // 找到哨兵位置
        input[i] = key;
        if (i+1 < k) QuickSort(input, i+1, r,k);
        if (i+1 > k) QuickSort(input, l, i-1,k);
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k){
        ArrayList<Integer> ret = new ArrayList<>();
        if (k > input.length){ // 本题说明条件
            return ret; // 空数组
        }
        QuickSort(input, 0, input.length-1,k);
        for (int i = 0; i < k; i++) {
            ret.add(input[i]);
        }
        return ret; 
    }
}