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

题目

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

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

Java题解

//时间复杂度O(nlogk)
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //PriorityQueue<Integer> heap=new PriorityQueue<Integer>((n1,n2)->n1-n2);//小根堆
        PriorityQueue<Integer> heap=new PriorityQueue<Integer>();//默认小根堆
        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: 父节点的值大于或等于子节点的值。

方法	功能
add(Element e)	队尾添加元素
clear()	清空整个列队
contains(Object o)	检查是否包含当前参数元素,返回布尔类型
offer(E e)	添加元素
peek()	访问队首元素（不删除）
poll()	取出队首元素，（删除）
remove(Object o)	根据value删除指定元素
size()	返回长度
isEmpty()	判断队列是否为空，返回布尔类型

PriorityQueue默认小根堆

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

PriorityQueue实现大根堆

方法一：重写compare方法

PriorityQueue<Integer> MaxHeap=new PriorityQueue<>(new Comparator<Integer>() {
    @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<Integer> MaxHeap=new PriorityQueue<Integer>((n1,n2)->n2-n1);