```
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return findK(nums, 0, nums.size() - 1, k);
}
int findK(vector<int> &nums, int st, int ed, int k) {
//cout << "call" << st << " " << ed << " " << k << endl;
if (st >= ed) return nums[st];
int i = st, j = ed, tmp;
int x = nums[i];
while (i <= j) {
while (nums[i] < x) i++;
while (nums[j] > x) j--;
if (i <= j) {
tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++; j--;
}
}
if (ed - i + 1 >= k) return findK(nums, i, ed, k);
if (ed - j < k) return findK(nums, st, j, k - (ed - j));
return nums[j + 1]; //In this case, there could only be one number between i and j
}
};
```