题解 | #最小的K个数#

此文仅用于本人记录

直接莽排序，貌似得益于快排，也不会超时，暂时没看见更容易记的算法思路，就先这样吧：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        quickSnort(input,0,input.length-1);
        int[] result = new int[k];
        for(int i = 0;i < k;i++){
            result[i] = input[i];
        }
        return (ArrayList<Integer>) Arrays.stream(result).boxed().collect(Collectors.toList());
    }
    void quickSnort(int[] arr,int start,int end){
        if(start < end){
            int i = start;
            int key = arr[start];
            for(int j = i + 1;j <= end;j++){
                if(key > arr[j]){
                    swap(arr,++i,j);
                }
            }
            arr[start] = arr[i];
            arr[i] = key;
            quickSnort(arr,start,i-1);
            quickSnort(arr,i+1,end);
        }
    }
    void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

然后发现只超过了4%的人，于是想问题应该出在：

Arrays.stream(result).boxed().collect(Collectors.toList());

就修改了下快排类型：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
       ArrayList in = new ArrayList();
        for(int i = 0; i < input.length;i++){
            in.add(input[i]);
        }
        quickSnort(in,0,input.length-1);
        ArrayList<Integer> result = new ArrayList<>(in.subList(0,k));
        return result;
    }
    void quickSnort(ArrayList<Integer> arr, int start, int end){
        if(start < end){
            int i = start;
            int key = arr.get(start);
            for(int j = i + 1;j <= end;j++){
                if(key > arr.get(j)){
                    swap(arr,++i,j);
                }
            }
            arr.set(start,arr.get(i));
            arr.set(i,key);
            quickSnort(arr,start,i-1);
            quickSnort(arr,i+1,end);
        }
    }
    void swap(ArrayList<Integer> arr,int i,int j){
        int temp = arr.get(i);
        arr.set(i,arr.get(j));
        arr.set(j,temp);
    }
}

注意subList方法需要new一次才能转类型，否则报错无法转换类型。
就超过了38%的人。。。
好吧先这样2333