题目：

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)。

Continue reading LeetCode #215 Kth Largest Element in an Array (查找数组中第K大的数)→