215. Kth Largest Element in an Array

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.

Solution:

1. Use array.sort to sort the array and get the n-k th element. It is simple and pretty efficient.

2. Quick selection, please refer to the quick sort basically, you pick an element between start and end as a pivot, and put all smaller numbers to its left and larger numbers to its right, so the position of the pivot will be the correct position in the sorted array. So if the position ==k return the pivot, if position< k find another pivot between position+1 to the end, else if position > k find another pivot between start and position -1 .

Average run time O(n), worst case O(n^2), 

To improve the efficiency, we usually randomly pick a pivot instead of choosing the beginning or the end of the array.

  public int findKthLargest(int[] nums, int k) {  
    return findKthNumber(nums,0,nums.length-1,nums.length-k);  
   }  
   public int findKthNumber(int[] nums, int s, int e,int k){  
     int pos=(int)(Math.random() * (e-s+1)+s);  
     swap(nums,pos,e);  
     int l=s;  
     int r=e-1;  
     while(l<=r){  
       if(nums[l]>=nums[e]){  
       swap(nums,l,r--);   
       }  
       else l++;  
     }  
     if(l==k) return nums[e];  
     swap(nums,e,l);  
     if(l<k) return findKthNumber(nums, l+1,e,k);  
     return findKthNumber(nums,s,l-1,k);  
   }  
   public void swap(int[] nums, int i, int j){  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }