题解 | #最小的K个数#快速排序以及小顶堆计算

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        findKBig(input,0,input.length-1,k-1);
        for(int i=0;i<k;i++){
            res.add(input[i]);
        }
        //通过快速排序计算结果
        //return res;
        //通过小顶堆计算结果
        return findKBig2(input,k);
    }
    //常规的快排
    public static void sort(int[] arr,int lo,int hi){
		if(lo >= hi){
			return;
		}
		int p = quickSort(arr,lo,hi);
		sort(arr,lo,p-1);
		sort(arr,p+1,hi);
	}
    //通过快排找第k大，那么k之前的数都比它小
	public static void findKBig(int[] arr,int lo,int hi,int k){
		if(lo>= hi){
			return;
		}
		while(lo < hi){
			int p = quickSort(arr,lo,hi);
			if( p < k){
				lo = p+1;
			}else if( p > k){
				hi = p-1;
			}else{
				return;
			}
		}
	}
	private static int quickSort(int[] arr, int i, int j) {
		int lo = i, hi = j;
		int key = arr[lo];
		while( lo < hi ){
			while(lo <hi && key <= arr[hi]){
				hi--;
			}
			while(lo <hi && key >= arr[lo]){
				lo++;
			}
			exchange(arr,lo,hi);
		}
		exchange(arr,i,lo);
		return lo;
	}
	public static void exchange(int[] arr,int i,int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
    
    //通过小顶堆来处理
    public static ArrayList<Integer> findKBig2(int[] arr,int k){
		ArrayList<Integer> res = new ArrayList<>();
                //将默认的大顶堆转为小顶堆
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>((i,j)->(j-i));
		for(int x: arr){
			pq.offer(x);
			if(pq.size()>k){
				pq.poll();
			}
		}
		while(!pq.isEmpty()){
			res.add(pq.remove());
		}
		return res;
	}
}