3 C++ solutions (O(NlogN) sort, O(klogN) heapsort, O(n) average quicksort-kind )


  • 10
    D

    First version, using std::sort, and return the k-th (from the end) entry

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            std::sort(nums.begin(), nums.end());
            return nums[nums.size()-k];
    }
    };
    

    Second version, using a heap, and pop up k-1 entries, the left top one is what we need

    int findKthLargest(vector<int>& nums, int k) {
        make_heap(nums.begin(), nums.end());
        for(auto i=0; i<k-1;i++)
        {
            pop_heap(nums.begin(), nums.end());
            nums.pop_back();
        }
        return nums.front();
    

    Third one, do quicksort, use the first entry as pivot and divide the array in two parts, the first half is the one no less than pivot and the second half is the one less then pivot. Then based on the length of the first half, decide to proceed in which half.

    int findKthLargest(vector<int>& nums, int k) {
        int i, m,n, pivot, head =0, tail=nums.size()-1, maxV;
        
        while(1)
        {
            m = head, n= tail;
            pivot = nums[m++];
            while(m<=n)
            {
                if(nums[m]>=pivot) m++;
                else if(nums[n]<pivot) n--;
                else {swap(nums[m++], nums[n--]);}
            }
            if(m-head == k) return pivot;
            else if(m-head < k) {k -= (m-head); head = m;  }
            else {tail = m-1;head = head+1;}
        }
    
    }
    

    };


  • 0
    K
    This post is deleted!

  • 0
    D

    You can check. Making a heap is not that expensive


  • 0
    K
    This post is deleted!

  • 0
    C

    I think you have to change if(nums[m]>=pivot) m++; to if(nums[m]>=pivot && m<right) m++;


  • 0
    This post is deleted!

  • 0
    K
    This post is deleted!

  • 0
    M

    Thanks for sharing! Inspired by your QuickSelect iterative solution. This one is a little different .

    int findKthLargest(vector<int>& nums, int k) { //average O(n), worst case O(n2)
        if(k<1 || k>nums.size()) return -1;
        int start = 0, end = nums.size()-1;
        int pivot, l, r;
        while(1){        
            pivot = nums[start]; l = start; r = end; //set the pivot and checking window
    
            while(l <= r){
                if(nums[l] >= pivot) l++;
                else if(nums[r] <= pivot) r--;
                else {swap(nums[l], nums[r]);}
            }
            swap(nums[start], nums[r]); //pivot is fixed at index r, which is (r+1)th 
    
            if(k == r+1) return nums[r];
            else if(k > r+1) start = r+1; //move to pivot's right part
            else {end = r-1;} //move to pivot's left part
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.