Description：
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.
Credits: Special thanks to @mithmatt for adding this problem and creating all test cases.
解题思路：
首先看到题目的做法是先将该数组用sort从大到小排好序，然后再输出nums[k-1]。但这样的算法是将整个数组都已经排好序的，在某些情况下是可以不用排好序便得到了答案，即在第一轮的交换中则刚好是结果。于是则有了下面的从每一轮选择pivot排完之后对当前位置进行判断。T(n) = T(n/2) + O(n)，
class Solution { public: int partition(vector<int>& a, int left, int right){ int pivot = a[left], i = left, j = right; while(i < j) { while(i < j && a[j] < pivot) j--; if(i < j) { a[i] = a[j]; i++; } while(i < j && a[i] > pivot) i++; if(i < j) { a[j] = a[i]; j--; } } a[i] = pivot; return i; } int findKthLargest(vector<int>& nums, int k) { int l = 0, r = nums.size() -1; while(1){ int pos = partition(nums,l,r); if(pos == k-1) return nums[pos]; if(pos > k-1) r = pos-1; else l = pos + 1; } } };