题解 | #最小的K个数#

排序，输出k个数即可

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        Arrays.sort(input);
        ArrayList<Integer> ret = new ArrayList<>();
        int cnt = 0;
        int idx = 0;
        while(cnt < k){
            ret.add(input[idx++]);
            cnt++;
        }
        return ret;
    }
}

手写的快排

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        quick_sort(input,0,input.length - 1);
        ArrayList<Integer> ret = new ArrayList<>();
        int cnt = 0;
        int idx = 0;
        while(cnt < k){
            ret.add(input[idx++]);
            cnt++;
        }
        return ret;
    }
    
    public void quick_sort(int arr[],int l,int r){
        if(l >= r)return;
        int i = l - 1,j = r + 1;
        int mid = arr[l + r >> 1];
        while(i < j){
            do{
               i++;
            }while(arr[i] < mid);
            do{
                j--;
            }while(arr[j] > mid);
            if(i < j){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        quick_sort(arr,l,j);
        quick_sort(arr,j + 1,r);
    }
    
}