Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array‘s length.
思路：用priorityqueue建maxheap然后读出第几个。
public class Solution { public int findKthLargest(int[] nums, int k) { if(k>nums.length) { return 0; } PriorityQueue<Integer> res=new PriorityQueue<>((a,b)->(b-a)); for(int i=0;i<nums.length;i++) { res.offer(nums[i]); } int m=0; int count=0; while(count<k) { m=res.poll(); count++; } return m; } }
Solution2:
discussion的一种解法特别巧妙。用java自带的minheap，size小于k就加数，大于k就减掉最小的，这样子就能保证queue最顶端的就是最k大的。最后退出循环返回的就是第k大的数。
public class Solution { public int findKthLargest(int[] nums, int k) { if(k>nums.length) { return 0; } PriorityQueue<Integer> res=new PriorityQueue<>(); for(int i=0;i<nums.length;i++) { res.offer(nums[i]); if(res.size()>k) { res.poll(); } } return res.poll(); } }
215. Kth Largest Element in an Array
原文：http://www.cnblogs.com/Machelsky/p/5904870.html