C++ solutions by applying heap


  • 0
    L

    Generally applying the property of heap - anytime the top value of the heap should be the maximum. Solution #1 is to write my own heap:

    class Solution {
        public:
            int findKthLargest(vector<int>& nums, int k) {
                vector <int> heap;
                for (int i(0);i<nums.size();i++) {
                addNodes(heap,nums[i]);
            }
            for (int i(0);i<k-1;i++) {
                removeNodes(heap);
            }
            return heap[0];
        }
        void addNodes(vector<int> &heap, int val) {
            heap.push_back(val);
            int ichild(heap.size()-1);
            int iparent((ichild-1)/2);
            while (heap.size()>1 && heap[ichild]>heap[iparent]) {
                swap(heap[iparent],heap[ichild]);
                ichild=iparent;
                iparent=(ichild-1)/2;
            }
        }
        void removeNodes(vector<int> &heap) {
            if (!heap.size()) return;
            heap[0]=heap[heap.size()-1];
            heap.pop_back();
            int iparent(0),ichildl(1),ichildr(2),ichild;
            while (ichildl<heap.size()) {
                if (ichildr<heap.size()) ichild=(heap[ichildl]>heap[ichildr]?ichildl:ichildr);
                else ichild=ichildl;
            
                if (heap[ichild]>heap[iparent]) swap(heap[ichild], heap[iparent]);
                else break;
            
                iparent=ichild;
                ichildl=iparent*2+1;
                ichildr=iparent*2+2;
            }
        }
    };
    

    The alternative and "lazy":-) solution is to apply the heap container "priority_queue", which will make the code very short and clean!

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            priority_queue<int> heap;
            for (int i(0);i<nums.size();i++) {
                heap.push(nums[i]);
            }
            for (int i(0);i<k-1;i++) heap.pop();
            return heap.top();
        }
    };

Log in to reply
 

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