• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【数据结构】算法 Kth Largest Element in an Array 数组中的第K个最大元素

开发技术 开发技术 6小时前 5次浏览

目录
  • Kth Largest Element in an Array 数组中的第K个最大元素
  • 思路
  • Tag

Kth Largest Element in an Array 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
 

思路

可以通过小顶堆, 并且将堆大小保持在k。此时堆顶节点都是需要的结果。

 public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->o1-o2);
        for (int i = 0; i < nums.length; i++) {
            pq.offer(nums[i]);

            if(pq.size()>k){
               pq.poll();
            }
             
        }
        return pq.peek();
    }

Tag

heap


喜欢 (0)