Kth Largest Element in an Array Solutions in C++

// Source : https://leetcode.com/problems/kth-largest-element-in-an-array/
// Author : Hao Chen
// Date   : 2015-06-11






class Solution {
public:
    //STL using qsort to solve this problem
    int findKthLargest_buildin(vector<int>& nums, int k) {
        int n=nums.size();
        std::nth_element(nums.begin(),nums.end()-k,nums.end());
        return nums[n-k];
    }
    
    //qsort partition
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left];
        int l = left + 1, r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot){
                swap(nums[l++], nums[r--]);
            }
            if (nums[l] >= pivot) l++;
            if (nums[r] <= pivot) r--;
        }
        swap(nums[left], nums[r]);
        return r;
    }
    
    int findKthLargest_qsort(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (true) {
            int pos = partition(nums, left, right);
            if (pos == k - 1){ 
                return nums[pos];
            }
            if (pos > k - 1) {
                right = pos - 1;
            }else{
                left = pos + 1;  
            }  
        }
    }
    
    
    int findKthLargest(vector<int>& nums, int k) {
        return findKthLargest_qsort(nums, k);
    }
};

/// Source : https://leetcode.com/problems/kth-largest-element-in-an-array/
/// Author : liuyubobobo
/// Time   : 2018-01-07

#include <iostream>
#include <vector>
#include <cassert>
#include <stdexcept>
#include <ctime>

using namespace std;


/// Sorting
/// Time Complexity:  O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        sort(nums.begin(), nums.end(), [](int a, int b){return a > b;});
        return nums[k - 1];
    }
};


int main() {

    vector<int> nums1 = {3, 2, 1, 5, 6, 4};
    cout << Solution().findKthLargest(nums1, 2) << endl;
    // 5

    vector<int> nums2 = {3, 1, 2, 4};
    cout << Solution().findKthLargest(nums2, 2) << endl;
    // 3

    vector<int> nums3 = {3, 3, 3, 3, 3, 3, 3, 3, 3};
    cout << Solution().findKthLargest(nums3, 8) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/kth-largest-element-in-an-array/
/// Author : liuyubobobo
/// Time   : 2018-01-07

#include <iostream>
#include <vector>
#include <cassert>
#include <stdexcept>
#include <ctime>
#include <queue>

using namespace std;


/// Using Min Heap to store the k largest elements
/// Time Complexity:  O(nlogk)
/// Space Complexity: O(k)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        priority_queue<int, vector<int>, greater<int>> pq;
        for(int e: nums)
            if(pq.size() != k)
                pq.push(e);
            else if(e > pq.top()){
                pq.pop();
                pq.push(e);
            }

        return pq.top();
    }
};


int main() {

    vector<int> nums1 = {3, 2, 1, 5, 6, 4};
    cout << Solution().findKthLargest(nums1, 2) << endl;
    // 5

    vector<int> nums2 = {3, 1, 2, 4};
    cout << Solution().findKthLargest(nums2, 2) << endl;
    // 3

    vector<int> nums3 = {3, 3, 3, 3, 3, 3, 3, 3, 3};
    cout << Solution().findKthLargest(nums3, 8) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/kth-largest-element-in-an-array/
/// Author : liuyubobobo
/// Time   : 2017-01-20

#include <iostream>
#include <vector>
#include <cassert>
#include <stdexcept>
#include <ctime>

using namespace std;


/// Based on Quick Sort Partition.
/// Time Complexity:  O(n)
/// Space Complexity: O(logn)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        srand(time(NULL));
        return findKthLargest(nums, 0, nums.size()-1 , k - 1 );
    }

private:
    int findKthLargest(vector<int>& nums, int l, int r, int k){

        if( l == r )
            return nums[l];

        int p = partition(nums, l, r);

        if( p == k )
            return nums[p];
        else if( k < p )
            return findKthLargest(nums, l, p-1, k);
        else // k > p
            return findKthLargest(nums, p+1 , r, k);
    }

    int partition( vector<int>& nums, int l, int r ){

        int p = rand()%(r-l+1) + l;
        swap( nums[l] , nums[p] );

        int lt = l + 1; //[l+1...lt) > p ; [lt..i) < p
        for( int i = l + 1 ; i <= r ; i ++ )
            if( nums[i] > nums[l] )
                swap(nums[i], nums[lt++]);

        swap(nums[l], nums[lt-1]);

        return lt-1;
    }
};


int main() {

    vector<int> nums1 = {3, 2, 1, 5, 6, 4};
    cout << Solution().findKthLargest(nums1, 2) << endl;
    // 5

    vector<int> nums2 = {3, 1, 2, 4};
    cout << Solution().findKthLargest(nums2, 2) << endl;
    // 3

    vector<int> nums3 = {3, 3, 3, 3, 3, 3, 3, 3, 3};
    cout << Solution().findKthLargest(nums3, 8) << endl;
    // 3

    return 0;
}