4ms c++ solution fastest


  • 0
    M

    class Solution {
    public:

    typedef struct heap {
        int *arr;
        int size;
    }heap;
    
    void swap(int *a,int *b)
    {
        int temp=*a;
        *a=*b;
        *b=temp;
    }
    
    void minheapify(heap *h,int i)
    {
        int l=2*i+1;
        int r=2*i+2;
        int s=i;
        if(l<h->size && (h->arr[l]<h->arr[i]))
            s=l;
        if(r<h->size && (h->arr[r]<h->arr[s]))
            s=r;
        if(s!=i)
        {
            swap(&h->arr[i],&h->arr[s]);
            minheapify(h,s);
        }
    }
    heap *createHeap(int arr[],int size)
    {
        heap *h=(heap *)malloc(sizeof(heap));
        h->arr=arr;
        h->size=size;
        for(int i=(h->size-2)/2;i>=0;i--)
            minheapify(h,i);
        return h;
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        int n=nums.size();
        int *arr=&nums[0];
        heap *h=createHeap(arr,k);
        for(int i=k;i<n;i++)
        {
            if(nums[i]>h->arr[0])
            {
                h->arr[0]=nums[i];
                minheapify(h,0);
            }
        }
        return h->arr[0];
    }
    

    };


Log in to reply
 

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