search

larscheng / algo

0 stars 0 forks source link

【Day 85 】2024-02-08 - 215. 数组中的第 K 个最大元素 #85

Open larscheng opened 8 months ago

larscheng commented 8 months ago

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

larscheng commented 8 months ago

思路

优先队列小顶堆 堆容量为k，超出容量就丢弃堆顶小的元素，最终堆顶就是第k大

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //小顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o1-o2);

        for (int i = 0; i < nums.length; i++) {
            queue.offer(nums[i]);
            if (queue.size()>k){
                queue.poll();
            }
        }
        return queue.peek();
    }
}

复杂度