kth_largest_element_in_an_array.cc

class Solution {
    int getPivotIndex(int& l, int& r) {
        return l + (r - l) / 2;
        //return l + rand() % (r - l + 1);
    }
    
    int partition(vector<int>& A, int& l, int& r) {
        int i = l, pivotIndex = getPivotIndex(l, r), pivot = A[pivotIndex];
        
        swap(A[pivotIndex], A[r]);
        
        for (int j = l; j < r; j++)
            if (A[j] > pivot)
                swap(A[i++], A[j]);
        
        swap(A[i], A[r]);
        
        return i;
    }
public:
    // Quickselect, O(n^2) worst case, O(n) average case, O(1) space if we can modify the input directly
    int findKthLargest(vector<int>& A, int& k) {
        int l = 0, r = A.size() - 1, mid;
        
        while (l < r) {
            mid = partition(A, l, r);
            
            if (mid + 1 == k) return A[mid];
            
            if (mid + 1 > k) r = mid - 1;
            else l = mid + 1;
        }
        
        return A[l];
    }
  
    // Priority queue (min heap), O(n log k) time and O(k) space
    int findKthLargestMinHeap(const vector<int>& nums, int& k) {
        priority_queue<int, vector<int>, greater<int>> pq(begin(nums), begin(nums) + k);

        int n = nums.size();

        for (int i = k; i < n; i++)
            if (nums[i] > pq.top()) {
                pq.pop();
                pq.push(nums[i]);
            }

        return pq.top();
    }
};