大顶堆或者小顶堆PriorityQueue解决TopK和k个最值问题

今天药忘吃喽~ 2023-10-13 19:47 19阅读 0赞

### 1. PriorityQueue用法 ###

容量k，默认为小根堆，即堆顶的元素为堆的最小值。

PriorityQueue<Integer> queue = new PriorityQueue<>(K);

通过lambdas表达式设置排序方式，这里设置大顶堆，即堆顶的元素为堆的最大值。

PriorityQueue<Integer> queue = new PriorityQueue<>(K, (o1, o2) -> o2 - o1);

### 2. 第k个值的问题 ###

如果是第k大，则可以用大顶堆排序，依次弹出k-1个数，则堆顶元素就是第k大。  
如果是第k小，则可以用小顶堆排序，依次弹出k-1个数，则堆顶元素就是第k小。

牛客第BM47 题：寻找第K大

public class Solution {
        
        public int findKth (int[] a, int n, int K) {
        
            if (n <= 0) {
        
                return -1;
            }
            //第k大，按照从大到小排序，取第k个就可以。
            PriorityQueue<Integer> queue = new PriorityQueue<>(K, (o1, o2) -> o2 - o1);
            for (int i = 0; i < n; i++) {
        
                queue.add(a[i]);
            }
            for (int i = 0; i < K - 1; i++) {
        
                queue.poll();
            }
            return queue.poll();
        }
    }

### 3. 最大或者最小的k个值 ###

如果是k大，则可以用大顶堆排序，依次弹出k个数。  
如果是k小，则可以用小顶堆排序，依次弹出k个数。

牛客BM46 最小的K个数：

public class Solution {
        
        public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        
            ArrayList<Integer> res = new ArrayList<>();
            if (input.length == 0 || k == 0) {
        
                return res;
            }
            //最小的k个数，按照从小到大排序，取前k个就可以。
            PriorityQueue<Integer> queue = new PriorityQueue<>(k);
            for (int i = 0; i < input.length; i++) {
        
                queue.add(input[i]);
            }
            for (int i = 0; i < k; i++) {
        
                res.add(queue.poll());
            }
            return res;
        }
    }