题解 | #最小的K个数#

NC119 最小的K个数

各种能排序的方式，都能解决；看了复杂度要求，最合适的就是二分查找。

//最近喜欢stream流 
import java.util.*;
import java.util.stream.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res =new ArrayList<Integer>();
        if(k<1) return res;
        Queue<Integer> aqueue=Arrays.stream(input)
            .boxed()
            .sorted()
            .collect(Collectors.toCollection(ArrayDeque::new));
        while(k-->0){
           res.add(aqueue.poll());
        }
        return res;
    }
}

队列是个好东西，尤其是优先队列。

import java.util.*;
import java.util.stream.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((x,y)->y-x);//大根堆
        ArrayList<Integer> res =new ArrayList<Integer>();//
        if(k<1) return res;
        int i=0;
        while(i<k){
           queue.offer(input[i]);
            i++;
        }
        while(i<input.length){
            if (queue.peek() > input[i]){
                queue.poll();
                queue.offer(input[i]);
            }
            i++;
        }
        while(k-->0){
           res.add(queue.poll());
        }
        return res;
    }
}