题目
此题与上一题一样,上到替我们采用快排,这次我们使用堆排 为什么使用堆排序是因为java特性本题是求前 K 小,因此用一个容量为 K 的大根堆,每次 poll 出最大的数,那堆中保留的就是前 K 小啦(注意不是小根堆!小根堆的话需要把全部的元素都入堆,那是 O(NlogN)O(NlogN),就不是 O(NlogK)O(NlogK)啦~~) 这个方法比快排慢,但是因为 Java 中提供了现成的 PriorityQueue(默认小根堆),所以实现起来最简单,没几行代码~
// 保持堆的大小为K,然后遍历数组中的数字,遍历的时候做如下判断: // 1. 若目前堆的大小小于K,将当前数字放入堆中。 // 2. 否则判断当前数字与大根堆堆顶元素的大小关系,如果当前数字比大根堆堆顶还大,这个数就直接跳过; // 反之如果当前数字比大根堆堆顶小,先poll掉堆顶,再将该数字放入堆中。 class Solution { public int[] getLeastNumbers(int[] arr, int k) { if (k == 0 || arr.length == 0) { return new int[0]; } // 默认是小根堆,实现大根堆需要重写一下比较器。 Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1); for (int num: arr) { if (pq.size() < k) { pq.offer(num); } else if (num < pq.peek()) { pq.poll(); pq.offer(num); } } // 返回堆中的元素 int[] res = new int[pq.size()]; int idx = 0; for(int num: pq) { res[idx++] = num; } return res; } }
// 保持堆的大小为K,然后遍历数组中的数字,遍历的时候做如下判断:// 1. 若目前堆的大小小于K,将当前数字放入堆中。// 2. 否则判断当前数字与大根堆堆顶元素的大小关系,如果当前数字比大根堆堆顶还大,这个数就直接跳过;// 反之如果当前数字比大根堆堆顶小,先poll掉堆顶,再将该数字放入堆中。class Solution { public int[] getLeastNumbers(int[] arr, int k) { if (k == 0 || arr.length == 0) { return new int[0]; } // 默认是小根堆,实现大根堆需要重写一下比较器。 Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1); for (int num: arr) { if (pq.size() < k) { pq.offer(num); } else if (num < pq.peek()) { pq.poll(); pq.offer(num); } } // 返回堆中的元素 int[] res = new int[pq.size()]; int idx = 0; for(int num: pq) { res[idx++] = num; } return res; }}
作者:sweetiee链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。