题目:
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.
链接: http://leetcode.com/problems/kth-largest-element-in-an-array/
7/16/2017
偷懒用了priority queue，并且把所有元素都放进了pq当中，没有限制pq的大小--这里导致时间复杂度有变化：
如果是pq size k: 总是保存最大的k个值，time complexity: O(k + (N - k)logk) = O(Nlogk)
如果size是N: time complexity: O(NlogN)
注意第6行开头用Queue而不是PriorityQueue
可以用heap，Radix sort或者Quick-Select
O(NlogN):
1 public class Solution { 2 public int findKthLargest(int[] nums, int k) { 3 int len = nums.length; 4 int n = len - k; 5 6 Queue<Integer> pq = new PriorityQueue<Integer>(); 7 for (int i = 0; i < nums.length; i++) { 8 pq.add(nums[i]); 9 } 10 for (int i = 0; i < n; i++) { 11 pq.poll(); 12 } 13 return pq.poll(); 14 } 15 }
O(Nlogk)即只保存最大的k个值的做法：（算法书Algorithm 6B）
1 public class Solution { 2 public int findKthLargest(int[] nums, int k) { 3 int len = nums.length; 4 5 Queue<Integer> pq = new PriorityQueue<Integer>(); 6 for (int i = 0; i < nums.length; i++) { 7 if (pq.size() < k) { 8 pq.offer(nums[i]); 9 } else { 10 if (nums[i] > pq.peek()) { 11 pq.poll(); 12 pq.offer(nums[i]); 13 } 14 } 15 } 16 return pq.peek(); 17 } 18 }
别人的答案
https://discuss.leetcode.com/topic/14597/solution-explained
更多讨论
https://discuss.leetcode.com/category/223/kth-largest-element-in-an-array
215. Kth Largest Element in an Array
原文：http://www.cnblogs.com/panini/p/7192644.html