题目描述
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
思路
- 此问题属于TopK问题,题目中要求取最小的数,所以是建立大根堆。
2.可以借助java原生的优先级队列,底层就是按照建堆思想实现的。
Java代码实现
import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { if(k>input.length || k==0){ return new ArrayList<>(); } PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,(o1,o2)->(o2-o1)); for (int i = 0; i <input.length; i++) { if(priorityQueue.size()<k){ priorityQueue.add(input[i]); }else{ if(priorityQueue.peek()>input[i]){ priorityQueue.poll(); priorityQueue.add(input[i]); } } } return new ArrayList<>(priorityQueue); } }