Kth Largest Element in an Array

LeetCode #215


Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.


For example,
Given [3,2,1,5,6,4] and k = 2, return 5.



Time: O(n).


class Solution {
    int findKthLargest(vector<int>& nums, int k) {

        int result = quickSelect(nums, 0, nums.size()-1, k);

        return result;


    int quickSelect(vector<int>& nums, int p, int q, int k){
        if(k>0 && k <= q-p+1){
            int r = partition(nums, p, q);
            if(r - p == k-1) return nums[r];
            else if(r - p > k-1) return quickSelect(nums, p, r-1, k);
            else return quickSelect(nums, r+1, q, k - (r-p + 1) );

        return INT_MAX;

    int partition(vector<int>& nums, int p, int q){
        int i = p-1;
        int last = q;
        for(int j=p; j<q; ++j){
            if(nums[j] > nums[last]){
                swap(nums[j], nums[++i]);
        swap(nums[++i], nums[last]);
        return i;

results matching ""

    No results matching ""