用堆解
两种实现方法
1）最大堆，o(klogn)
直接将原数组建堆 o(n)
然后弹出k次 (klogn)
返回最后一次poll()的值
1 class Solution { 2 public int findKthLargest(int[] nums, int k) { 3 if(nums.length == 0) 4 return 0; 5 PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); 6 int res = 0; 7 for(int num : nums) 8 pq.offer(num); 9 10 while(k != 0){ 11 res = pq.poll(); 12 k--; 13 } 14 15 return res; 16 } 17 }
2)最小堆
用数组前k个数建堆 o(k)
剩下n-k，依次插入堆中然后推出堆顶元素o((n-k)logk)
剩下的k个肯定是前k大的数，只要返回此时堆顶即可
leetcode 215 Kth Largest Element in an Array
原文：https://www.cnblogs.com/hwd9654/p/10926181.html