Time Limit Exceeded


  • 0
    H

    My idea is to pick the smallest value at a time. But why it exceeds time limit? Anybody can help me? Thanks.

    class Solution {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            int k = lists.size();
            int minidx;
            bool onlyoneleft = false;
            ListNode *head, **cursor = &head, *walk;
            ListNode *pidxarray[k];
            for(int i = 0; i < k; i++)
                pidxarray[i] = lists[i];
                
            if(empty(pidxarray,k))
                return NULL;
            while(!empty(pidxarray,k)){
                walk = findminimum(pidxarray,k,&minidx,&onlyoneleft);
                if(onlyoneleft){
                    *cursor = walk;
                    return head;
                }
              //  pidxarray[minidx] = pidxarray[minidx]->next;
                *cursor = walk;
                cursor = (&(*cursor)->next);
            }
            
        }
        
        ListNode *findminimum(ListNode **parray, int num, int *minidx,bool *theone){
            int i, nonnull = 0, theonlyone, idx;
            ListNode *minNode;
            for(i = 0;i < num;i++){
                if(parray[i]) {
                    nonnull++;
                    theonlyone = i;
                }
            }
            if(nonnull == 1){       //we have only one unmerged list
                *theone = true;
                return parray[theonlyone];
            }
            
            idx = theonlyone;
            
            for(i=0;i<num;i++){
                if(!parray[i])  continue;
                if(i != idx){
                    if(parray[i]->val < parray[idx]->val)
                        idx = i;
                }
            }
            
            minNode = parray[idx];
            parray[idx] = parray[idx]->next;
            *minidx = idx;
            
            return minNode;
        }
        
        bool empty(ListNode **parray, int num){
            int i = 0;
            for(;i<num;i++)
                if(parray[i])
                return false;
            return true;
        }
    };

  • 1
    T

    Because this is way too slow.... it seems that this strategy used to work before on LeetCode, but no longer so since new test cases have been added.

    Try divide and conquer -- picking the smallest value at a time requires scanning through the k lists every time, but most of these scanning operations are useless. It will be much better if you sub-divided these k lists recursively since every operation there contributes to building up the final list.


Log in to reply
 

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