Two ways: Heap based solution and modified quicksort


  • 0

    specialized quick sort

    int findKthLargest(vector<int>& nums, int k) {
        int l=0, r=nums.size(), i, j, idx;
        while( l < r ) {
            idx = (l + r)/2; 
            swap( nums[idx], nums[r-1] );
            i = l; j = l;
            while( i < r-1 ) {
                if( nums[i] >= nums[r-1] ) swap(nums[i++], nums[j++]);
                else i++;
            }
            swap(nums[r-1], nums[j++]);
            if( j-l > k ) r = j-1;
            else if( j-l == k ) return nums[j-1];
            else {
                k -= (j-l);
                l = j;
            }
        }        
        return nums[l+k-1];
    }
    

    heap solution

    class Solution {
    private:
        void createHeap(vector<int>& heap) {
            for( int i=heap.size()/2; i>=0; i-- ) {
                heapify(heap, i);
            }
        }
        void heapify(vector<int>& heap, int i) {
            if( i < heap.size() ) {
                int idx = i, val = heap[i];
                if( 2*i+1 < heap.size() && heap[2*i+1] < val ){
                    idx = 2*i + 1;
                    val = heap[2*i+1];
                }
                if( 2*i+2 < heap.size() && heap[2*i+2] < val ) {
                    idx = 2*i + 2;
                    val = heap[2*i+2];
                } 
                if( idx != i ) {
                    swap( heap[idx], heap[i] );
                    heapify(heap, idx);
                }
            }
        }
    public:
        int findKthLargest(vector<int>& nums, int k) {
            vector<int> heap(nums.begin(), nums.begin() + k);
            createHeap(heap);
            for( int i=k; i<nums.size(); i++) {
                if( nums[i] <= heap[0]) continue;
                heap[0] = nums[i];
                heapify( heap, 0 );
            }
            return heap.front();
        }
    };

Log in to reply
 

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