C++ using heap, but Time Limit Exceeded,help


  • 0
    C
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for(vector<ListNode *>::iterator i = lists.begin();i != lists.end();i++)
            if(*i == NULL)
                lists.erase(i--);
        int flag =0;
        ListNode *head,*result,*pre;
        int k = lists.size();
        if(k == 0) return NULL;
        if(k == 1) return lists[0];
        buildMinHeap(lists);
        result = lists[0];
        while(true){
            if(flag == 0){
                head = lists[0];
                flag++;
            }
            else
                head->next = lists[0];
            lists[0] = lists[0]->next;
            head = head->next;
            if(lists[0] != NULL){
                minHeapDown(lists,0,lists.size());
            }
            else{
                    lists[0] = lists[lists.size()-1];
                    lists.pop_back();
                    if(lists.size() == 0)
                        head->next = NULL;
                        return result->next;
                    minHeapDown(lists,0,lists.size());
                }
            }
    }
    
    void buildMinHeap(vector<ListNode *> &lists){
        int k = lists.size();
        for(int i = k/2;i >= 0 ;i--)
            minHeapDown(lists,i,k);
    }
    
    void minHeapDown(vector<ListNode *> &lists,int i,int k){
        int child;
        ListNode *tmp;
        for(tmp = lists[i];(i*2+1) < k;i = child){
            child = i*2+1;
            if(child != k-1 && lists[child+1]->val < lists[child]->val) child++;
            if(tmp->val > lists[child]->val){
                lists[i] = lists[child];
            }else{
                break;
            }
        }
        lists[i] = tmp;
        }

Log in to reply
 

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