[c++]Why my minimum heap implementation time exceeded?


  • 0
    A

    My code is below:

    class Solution {
    public:
        void change(ListNode*& a, ListNode*& b)
        {
            if(!b) {
                return;
            } else if(!a) {
                a = b;
                b = nullptr;
            } else if(a->val > b->val)
            {
                ListNode* tmp = a;
                a = b;
                b = tmp;
            }
        }
        
        ListNode* Process(vector<ListNode*>& lists)
        {
            int len = lists.size();
            int depth = log(len) / log(2);
            for(int i = depth - 1; i >= 0; i--)
            {
                int start = (int)pow(float(2), (float)i) - 1;
                int end = 2 * start + 1;
                for(int j = start; j < end; j++)
                {
                    if(j*2 + 1 < len)
                        change(lists[j], lists[j*2 + 1]);
                    if(j*2 + 2 < len)
                        change(lists[j], lists[j*2 + 2]);
                }
            }
            return lists[0];
        }
        
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size() == 0) return nullptr;
            if(lists.size() == 1) return lists[0];
            ListNode* head = new ListNode(0);
            ListNode* cur = head;
            ListNode* tmp;
            while((tmp = Process(lists)) != nullptr)
            {
                cur->next = tmp;
                if(nullptr == tmp->next) {
    		        lists[0] = lists.back();
    		        lists.pop_back();
    	        } else {
    		        lists[0] = tmp->next;
    	        }
                tmp->next = nullptr;
                cur = tmp;
    	        if(lists.size() == 1) {
    		        cur->next = lists[0];
    		        break;
     	        }
            }
            return head->next;
        }
    };

Log in to reply
 

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