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.

The same with Lintcode:

快速选择 Quick Select

复杂度

时间 Avg O(N) Worst O(N^2) 空间 O(1)

One thing to notice is 23-24 line, still find kth smallest element, do not need to decrease from k because the indexing(编号) does not change

1 public class Solution { 2     public int findKthLargest(int[] nums, int k) { 3         int len = nums.length; 4         return findKthSmallest(nums, 0, len-1, len-k+1); 5     } 6      7     public int findKthSmallest(int[] nums, int start, int end, int k) { 8         int l = start; 9         int r = end;10         int pivot = end;11         while (l < r) {12             while (l
     
      = nums[pivot]) {16                 r--;17             }18             if (l == r) break;19             swap(nums, l, r);20         }21         swap(nums, l, pivot);22         if (l+1 == k) return nums[l];23         else if (l+1 < k) return findKthSmallest(nums, l+1, end, k);24         else return findKthSmallest(nums, start, l-1, k);25     }26     27     public void swap(int[] nums, int l, int r) {28         int temp = nums[l];29         nums[l] = nums[r];30         nums[r] = temp;31     }32 }
     

 

优先队列

复杂度

时间 O(NlogK) 空间 O(K)

思路

遍历数组时将数字加入优先队列（堆），一旦堆的大小大于k就将堆顶元素去除，确保堆的大小为k。遍历完后堆顶就是返回值。

1 public class Solution { 2     public int findKthLargest(int[] nums, int k) { 3         PriorityQueue
     
       p = new PriorityQueue
      
       (); 4         for(int i = 0 ; i < nums.length; i++){ 5             p.add(nums[i]); 6             if(p.size()>k) p.poll(); 7         } 8         return p.poll(); 9     }10 }
      
     

用最大堆也可以，把所有元素加进去后，poll K次