力扣 215. 数组中的第K个最大元素

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

Java题解

//时间复杂度O(nlogk)
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //PriorityQueue heap=new PriorityQueue((n1,n2)->n1-n2);//小根堆
        PriorityQueue heap=new PriorityQueue();//默认小根堆
        for(int n:nums){
            heap.add(n);//队尾添加元素
            if(heap.size()>k)//返回长度大于k时，把最小值（即根结点）删掉，保留当前最大的k个结点
                heap.poll();//取出队首元素，（删除）
        }
        return heap.poll();
    }
}

Java知识点

 PriorityQueue详解 可以处理动态数据流

堆(Heap)分为小根堆和大根堆两种。Min-heap: 父节点的值小于或等于子节点的值；Max-heap: 父节点的值大于或等于子节点的值。

PriorityQueue默认小根堆

 PriorityQueue heap = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

PriorityQueue实现大根堆

方法一：重写compare方法

PriorityQueue MaxHeap=new PriorityQueue<>(new Comparator() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
});

方法二：lambda表达式

// 1. 不需要参数,返回值为 5  
() -> 5  
  
// 2. 接收一个参数(数字类型),返回其2倍的值  
x -> 2 * x  
  
// 3. 接受2个参数(数字),并返回他们的差值  
(x, y) -> x – y  
  
// 4. 接收2个int型整数,返回他们的和  
(int x, int y) -> x + y  
  
// 5. 接受一个 string 对象,并在控制台打印,不返回任何值(看起来像是返回void)  
(String s) -> System.out.print(s)

PriorityQueue MaxHeap=new PriorityQueue((n1,n2)->n2-n1);