首先复习一下quicksort.
先理解partition函数，就是选序列的最后一个数作为pivot，比它小的排到它左边，比它大的在它右边，它在中间。但是它左右的部分并没有排序。
返回值是这个pivot所在的位置，pivot所在位置就是它最终的位置，也就是说比如index是5，说明它就是第6大的数。
quicksort里面就是调用partition,不断对其左右进行排序，直到low >= high
partition伪代码
1 paritition(arr, low, hight): 2 3 index = low;//index是第一个不小于pivot的数的index 4 5 对于从low到high的数： 6 7 如果这个数比pivot小，那么： 8 把index和这个数交换 9 index++ 10 swap pivot和index所在的数 11 12 返回index
quicksort伪代码
1 quicksort(arr, low, high): 2 3 如果low<high: 4 5 partitionIndex = partition(arr, low, high); 6 partition(arr, low, partitionIndex - 1); 7 partition(arr, partitionIndex + 1, high);
所以这道题的思路就是，先partition一次，然后如果正好是第k-1个,那就返回，不然如果partition完左侧加起来的数字数目已经超过了k-1，那么说明右侧反正都小于这个pivot了，就只对左侧递归，不然就对右侧递归
1 public int findKthLargest(int[] nums, int k) { 2 if (nums.length == 1) { 3 return nums[0]; 4 } 5 int idx = -1; 6 int left = 0, right = nums.length - 1; 7 while (idx != k - 1) { 8 idx = partition(nums, left, right); 9 if(idx > k - 1) { 10 right = idx - 1; 11 } else { 12 left = idx + 1; 13 } 14 } 15 return nums[idx]; 16 } 17 18 private int partition(int[] nums, int low, int high) { 19 int index = low; 20 int pivot = nums[high]; 21 for(int i = low; i < high; i++) { 22 if(nums[i] > pivot) { 23 swap(nums, index, i); 24 index++; 25 } 26 } 27 swap(nums, index, high); 28 return index; 29 } 30 31 private void swap(int[] nums, int idx1, int idx2) { 32 int tmp = nums[idx1]; 33 nums[idx1] = nums[idx2]; 34 nums[idx2] = tmp; 35 }
另外一种方法是用PriorityQueue。
PQ的值得记录的：
1.自动维护从小到大的顺序，可以poll(),peek().但是不方便得到某一位置上的元素。
2.当然可以自己写comparator，但是如果单纯想逆序的话，可以new PQ<>(Collections.reverseOrder())
1 public int findKthLargest(int[] nums, int k) { 2 PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); 3 for(int i = 0; i < nums.length; i++) { 4 pq.offer(nums[i]); 5 if(pq.size() > k) { 6 pq.poll(); 7 } 8 } 9 return pq.poll(); 10 }
215. Kth Largest Element in an Array
原文：http://www.cnblogs.com/warmland/p/5700014.html