题目：
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.
分析：
查找无序数组中第K大的数。
最简单暴力的方法就是先对整个数组排序，然后返回 nums[k-1] 即可。时间复杂度O(nlogn)。
有没有更高效的方法呢？我们不妨参考快速排序的思路，但是不对整个数列排序。
partition(int[] a, int lo, int hi)方法和快速排序一样，选取该分段中的第一个数为标兵(pivot)。所有大于pivot的数放到其左侧，小于pivot的数放到其右侧。最后返回pivot的位置。在经过一次partition方法之后，根据k和pivot的位置，来选择是对左侧部分还是对右侧部分继续进行partition。该方法时间复杂度为O(n)。
例如，现在有数组[3, 2, 1, 5, 6, 4]，k=2。
在经过第1次partition之后，数组变为[4, 6, 5, 3, 1, 2]，pivot位置为第4个（从1开始计数）。我们要找的是第2大的数，小于pivot的位置，所以该数在pivot的左侧。继续对pivot左侧的部分进行partition。
在经过第2次partition之后，数组变为[5, 6, 4, 3, 1, 2]，pivot位置为第3个（从1开始计数）。继续对pivot左侧的部分进行partition。
在经过第3次partition之后，数组变为[6, 5, 4, 3, 1, 2]，pivot位置为第2个（从1开始计数）。这正是我们要查找的数。返回该数。
代码：
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public class Solution { public int findKthLargest(int[] nums, int k) { k--; int lo = 0; int hi = nums.length - 1; int index = 0; while(lo < hi){ index = partition(nums, lo, hi); if(k < index) hi = index - 1; else if(k > index) lo = index + 1; else return nums[index]; } return nums[lo]; } // Return the index of pivot after sort // Numbers on its left are greater, numbers on its right are smaller private int partition(int[] a, int lo, int hi){ int i = lo; int j = hi; int pivot = a[lo]; while(i < j){ while(i < j && a[j] <= pivot) j--; a[i] = a[j]; while(i < j && a[i] >= pivot) i++; a[j] = a[i]; } a[i] = pivot; return i; } } |