where my heap sort was TIME LIMIT EXCEEDED!


  • 0
    C

    class Solution {
    public:
    int findKthLargest(vector<int>& nums, int k) {
    if(nums.size()<k||k<1) return -1;
    if(nums.size()==1) return nums[0];

        //heap sort
        for(int i=(k-1)>>1;i>=0;i--)
            shiftdown(nums, i, k-1);
        for(int i=k;i<nums.size();i++){
            if(nums[i]>nums[0]){
                int tmp=nums[i];
                nums[i]=nums[0];
                nums[0]=tmp;
                shiftdown(nums, 0, k-1);
            }
        }
        return nums[0];
    }
    
    void shiftdown(vector<int>& nums, int s, int e){
        int tmp=nums[s];
        while(s<e){
            int c1 = (s<<1)+1;
            if(c1>e) break;
            if(c1+1<=e&&nums[c1+1]>nums[c1]) c1++;
            if(nums[s]>nums[c1]){
                nums[s]=nums[c1];
                s=c1;
            }
        }
        nums[s] = tmp;
    }
    

    };


Log in to reply
 

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