本题要求在一个数组中找出第k大的元素， 比如在[3,2,1,5,6,4]中找第2大的元素，函数应该返回5。 本题至少可以使用O(nlogn)的排序算法来将数组排序，课上讲过一种更好的类似快排的做法，今天做一下实现：
#include <vector> #include <cstdlib> #include <ctime> #include <utility> using namespace std; class Solution { public: int findKthLargest(vector<int>& nums, int k) { vector<int>::iterator begin = nums.begin(); vector<int>::iterator end = nums.end(); srand(time(NULL)); return findKthLargest1(begin, end, k); } int findKthLargest1(vector<int>::iterator begin, vector<int>::iterator end, int k) { if (begin >= end) return *begin; unsigned int idx = rand() % (end - begin); swap(*begin, *(begin + idx)); vector<int>::iterator r = begin, l = end - 1; int key = *begin; while (r < l) { while (key <= *l && l > r) l--; swap(*r, *l); while (key >= *r && r < l) r++; swap(*r, *l); } int larger_count = end - l; if (larger_count == k) return *l; else if (larger_count > k) return findKthLargest1(r + 1, end, k); else // larger_count < k return findKthLargest1(begin, l, k - larger_count); } };这里使用了分治思想，采用递归来实现该算法，当然也可以使用循环来实现。这里的实现是一个随机算法，首先在数组中随机找到一个数，将它与数组首个元素交换，然后使用快排中的划分方法，以矩阵首元素为key，将矩阵分为[ [小于key], key, [大于key]]3部分，然后就可以得知key是第larger_count大的数，若larger_count等于k就返回，否则根据larger_count和k的关系来决定在[小于key]中寻找，或在[大于key]中寻找。 这个算法的期望复杂度为O(n)，如果能在O(n)时间内找到的话则一定是这个问题最快的方法，但是这是一个随机算法，其最坏的复杂度为O(n^2)，总的来说，这种方法优于基于排序的O(nlogn)的方法。
