class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, k);
    }

private:
    int quickSelect(vector<int>& nums, int lo, int hi, int k)
    {
        if(lo == hi)return nums[lo];
        int num = nums[lo], i = lo + 1, j = hi;
        while(true)
        {
            while(i <= hi && nums[i] >= num)++i;
            while(j > lo && nums[j] <= num)--j;
            if(i > j)break;
            swap(nums[i], nums[j]);
        }
        swap(nums[lo], nums[j]);
        if(k == j + 1 - lo)return nums[j];
        else if(k < j + 1 - lo)return quickSelect(nums, lo, j - 1, k);
        else return quickSelect(nums, j + 1, hi, k - (j + 1 - lo));
    }
};