Sharing of my c++ solution using heap sort..


  • 0
    R
    class Solution {
    public:
        void swap(vector<int>& num,int i,int j) 
        {
            int temp=num[i];
            num[i]=num[j];
            num[j]=temp;
        }
        void max_heapfy(vector<int>& num,int index,int sz) {
            if(index<0||index>=sz)
                return;
            int left=2*index+1;
            int right=2*index+2;
    
            int larger=index;
    
            if(left<sz&&num[index]<num[left])
                larger=left;
    
            if(right<sz&&num[larger]<num[right])
                larger=right;
    
            if(larger!=index) 
            {
                swap(num,larger,index);
                max_heapfy(num,larger,sz);
            }
        }
        void heapfy(vector<int>& num,int index,int sz) {
            max_heapfy(num,index,sz);
        }
    
        void buildHeap(vector<int>& num) {
            int sz=num.size();
            for(unsigned int i=0;i<sz;i++)
                heapfy(num,sz-i-1,sz);
        }
        void print(vector<int>& nums)
        {
            cout<<"{ ";
            for(int i=0;i<nums.size();i++)
                cout<<nums[i]<<",";
            cout<<"}\n";
        }
        int findKthLargest(vector<int>& nums, int k) {
            buildHeap(nums);
            int sz=nums.size();
            for(int t=0;t<k;t++) 
            {
                swap(nums,0,sz-1);
                sz--;
                for(int i=sz-1;i>=0;i--)
                    heapfy(nums,i,sz);
            }
            sz=nums.size();
            return nums[sz-k]; 
        }
    
    };

Log in to reply
 

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