寻找第K大的数，可以有很多的方法。一般而言想到的最简单的方法都是先对数组进行排序，然后直接选择第K个数，就是第k大的数。这样做的话，时间为O(nlogn)。那是否还有更快的方法呢？
我们可以使用分治算法的思想。参考快速排序，寻找到一个中点pivot，该中点把左半部分和右半部分分开，右半部分的值均大于左半部分。若K < pivot，则对左半部分继续进行上述步骤，若K>pivot，对右半部分继续实行上述步骤。直到K = pivot时，pivot就是第K大的数。
这里即有快速排序的方法，也有二分查找的思想。
代码如下：
class Solution { public: //快速排序的方法 int findMiddle(vector<int>& nums, int left, int right) { int pivot = nums[left]; int L = left + 1, R = right; while (L <= R) { if (nums[L] < pivot && nums[R] > pivot) swap(nums[L++], nums[R--]); if (nums[L] >= pivot) L++; if (nums[R] <= pivot) R--; } swap(nums[left], nums[R]); return R; } int findKthLargest(vector<int>& nums, int k) { int left = 0, right = nums.size() - 1; //二分查找的方法 while (1) { int pos = findMiddle(nums, left, right); if (pos == k - 1) return nums[pos]; if (pos > k - 1) right = pos - 1; else left = pos + 1; } } };
如此，时间缩减为O(n)
