LeetCode-NOTES/Algorithms/215.Kth-Largest-Element-in-an-Array/solution.cpp at master · mkn-root12/LeetCode-NOTES · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        int L = 0, R = nums.size()-1;
        while(L < R)
        {
            int left = L, right = R;
            int key = nums[left];
            while(left < right)
            {
                while(left < right && nums[right] < key)
                    right--;
                nums[left] = nums[right];
                while(left < right && nums[left] >= key)
                    left++;
                nums[right] = nums[left];
            }
            nums[left] = key;
            if(left == k -1)
                return nums[k-1];
            else if (left > k-1)
                R = left - 1;
            else
                L = left + 1;
        }
        return nums[k-1];
    }
};