Kth Largest Numbers in Unsorted Array

2/20/2018 update
在quick selcct里面判断start > end没有必要。因为如果start > end，那么partition里面什么都不会干。
if (pivotIndex == k  - 1) so that all numbers before pivotIndex is smaller than nums[PI].

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length, k);
    }
    
    private int quickSelect(int[] nums, int start, int end, int k) {
        int pivotIndex = partition(nums, start, end);
        if (pivotIndex == k - 1) {
            return nums[pivotIndex];
        } else if (pivotIndex < k - 1) {
            return quickSelect(nums, pivotIndex + 1, nums.length, k);
        } else {
            return quickSelect(nums, start, pivotIndex, k);
        }
    } 
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private int partition(int[] nums, int start, int end) {
        int pivot = nums[start];
        int index = start + 1;
        for (int i = start + 1; i < end; i++) {
            if (nums[i] > pivot) {
                swap(nums, index++, i);
            }
        }
        swap(nums, start, index - 1);
        return index - 1;
    }
}

------------------------------------------------------------------------------------------------------


思路：
用quick sort的思想，这里叫quick select。
if( pivotIndex < k - 1) 在右边，反之则在左边。

 public class Solution {  
   /*  
    * @param k: An integer  
    * @param nums: An integer array  
    * @return: kth smallest element  
    */  
   public int kthSmallest(int k, int[] nums) {  
     // write your code here  
     return quickSelect(nums, 0, nums.length - 1, k);  
   }  
   // find kth smallest  
   private int quickSelect(int[] nums, int start, int end, int k) {  
     if(start > end) {  
       return Integer.MIN_VALUE;  
     }  
     int pivotIndex = partition(nums, start, end);  
     if(pivotIndex == k - 1)  
       return nums[pivotIndex];  
     else if(pivotIndex < k - 1) // right side  
       return quickSelect(nums, pivotIndex + 1, end, k);  
     else   
       return quickSelect(nums, start, pivotIndex - 1, k);  
   }  
   private void swap(int[] a, int i, int j) {  
     int tmp = a[i];  
     a[i] = a[j];  
     a[j] = tmp;  
  }  
  private int partition(int[] A, int start, int end) {  
     int pivotValue = A[start];  
     int storeIndex = start + 1;  
     for(int i = start + 1; i <= end; i++) {  
       // put value less then pivotValue to left  
       if(A[i] <  pivotValue) {  
         swap(A, storeIndex++, i);  
       }  
     }  
     // place the pivot in the middle  
     swap(A, start, storeIndex - 1);  
     // return the new pivot index  
     return storeIndex - 1;  
   }  
 }  

不明白为什么，在左边和右边都是找kth smallest.