题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路：
构建一个k大小的大根堆，遍历input数组，在堆未满时，直接存入元素，在堆已满时，则比较堆顶元素与带插入元素，若带插入元素更小，则替换堆顶元素。
import java.util.ArrayList; import java.util.Comparator; import java.util.PriorityQueue; public class GetLeastNumbers_Solution { //输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> list = new ArrayList<>(); if(input.length < k || k==0){ return list; } //优先队列默认是最小堆，此做法是构建一个大根堆 Comparator<Integer> comparator = new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }; PriorityQueue<Integer> queue = new PriorityQueue<>(k,comparator); //构建一个k大小的大根堆，遍历input数组，在堆未满时，直接存入元素，在堆已满时， //则比较堆顶元素与带插入元素，若带插入元素更小，则替换堆顶元素。 for(int i = 0 ; i<input.length ;i++){ if(i<k){ queue.add(input[i]); } else { if(input[i] < queue.peek()){ queue.remove(); queue.add(input[i]); } } } while (!queue.isEmpty()){ list.add(queue.poll()); } return list; } }小结：
优先队列默认为最小堆，优先队列构建最大堆的方法。
Comparator<Integer> comparator = new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }; PriorityQueue<Integer> queue = new PriorityQueue<>(k,comparator);优先队列主要的方法有：
queue.add() queue.offer(); //添加 ,前者添加失败 抛异常 后者添加失败 返回null queue.peek() queue.element(); //查看堆顶元素但不移除 前者查看失败 抛异常 ，后者 返回null queue.remove() queue.poll(); // 移除堆顶元素 ， 前者移除失败 抛异常 后者返回null