题目描述：

求数组中第k大的数。

思路：

快排思想。使用kuai分治每次将数组划分为两段，并且返回划分点的位置，如果这个位置恰好是我们要的第k大的数，那么返回这个数即可。 如果返回的位置小于要找的位置，则向右边的一半数组继续寻找。 如果返回的位置大于要找的位置，则向左边寻找。

代码：

class Solution { public: int partition(vector<int>& nums, int l, int r) { int val = nums[r]; for (int i=l; i<r; ++i) { if (nums[i] < val) { swap(nums[l++], nums[i]); } } swap(nums[l], nums[r]); return l; } int findKthLargest(vector<int>& nums, int k) { int len = nums.size(); int l = 0, r = len-1, pos = len - k; int ans; while((ans = partition(nums, l, r)) != pos) { ans < pos ? l = ans + 1 : r = ans - 1; } return nums[pos]; } };

这道题放那三天了，我终于写了。 看论文看的脑壳痛，好不容易看完abstract和introduction，发现好像，还是啥也没看懂。 刷题刷题，不要懒啊。