4ms c++ code use heap sort


  • 1
    Z

    code is simple
    1 create a small heap with size k
    2 for data between [k-1,size-1], check and modify the heap
    3 at last the heap top data is the K'th largest one.

    class Solution {
        void modifyHeap(vector<int>& nums, int index, int k)
        {
            int lc = 2*index+1;
            int rc = lc+1;
            if(lc>=k) return;
            
            int minv = nums[index];
            int minindex = index;
            if(lc<k && nums[lc]<minv)
            {
                minv = nums[lc];
                minindex = lc;
            }
            if(rc<k && nums[rc]<minv)
            {
                minv = nums[rc];
                minindex = rc;
            }
            if(minindex!=index)
            {
                swap(nums[minindex],nums[index]);
                modifyHeap(nums,minindex,k);
            }
        }
        void buildHeap(vector<int>& nums, int k)
        {
            int x = k/2-1;
            for(int i = x;i>=0;--i)
            {
                modifyHeap(nums,i,k);
            }
        }
    public:
        int findKthLargest(vector<int>& nums, int k) {
            int size ;
            if((size=nums.size()) == 0) return 0;
            if(size == 1)return nums[0];
            buildHeap(nums,k);
            for(int i = k;i<size;++i)
            {
                if(nums[i]>nums[0])
                {
                    swap(nums[i],nums[0]);
                    modifyHeap(nums,0,k);
                }
        
            }
            
            return nums[0];
            
        }
    };

  • 0
    W

    you can directly use make_heap, pop_heap and push_heap routines in c++ stl.


  • 0
    X

    std::priority_queue<int, std::vector<int>, std::greater<int>> is min heap which stores integer.


Log in to reply
 

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