LeetCode 215 Kth Largest Element in an Array

思路：跟找第kth小的数相反，数组逆向排序。从前找第k － 1个数。
 1 public class Solution {
 2     public int findKthLargest(int[] array, int k) {
 3         // Write your solution here
 4         if (array == null || array.length == 0) {
 5           return -1;
 6         }
 7 
 8         quickSelect(array, 0, array.length - 1, k);
 9         return array[k - 1];
10       }
11 
12       private void quickSelect(int[] array, int start, int end, int k) {
13         if (start >= end) {
14           return;
15         }
16         Random rand = new Random();
17         int pivot = start + rand.nextInt(end - start + 1);
18         swap(array, pivot, start);
19 
20         int left = start + 1, right = end;
21         while (left <= right) {
22           if (array[right] < array[start]) {
23             right--;
24           } else {
25             swap(array, left, right);
26             left++;
27           }
28         }
29         //最后left跟right错开后，left仍然指着第一个小于pivot的元素，right指着最后一个大于pivot的元素
30         swap(array, right, start);
31         if (k == right) {
32           return;
33         } else if (k < right) {
34           quickSelect(array, start, right - 1, k);
35         } else if (k > right) {
36           quickSelect(array, right + 1, end, k);
37         }
38       }
39 
40       private void swap(int[] array, int start, int end) {
41         int temp = array[start];
42         array[start] = array[end];
43         array[end] = temp;
44       }
45 }