13ms and O(2*k) space C solution with heap


  • 0
    A

    It ought to be more faster,but I'm tired,I have spend almost 3 hours to code this :(

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    void adjust_heap(int* heap,int* tag,int size,int parent){//adjust a heap with recursion
        int left_child=parent*2+1;
        int right_child=parent*2+2;
        if(right_child<size){
            int min_pos=heap[right_child]<heap[left_child]?right_child:left_child;
            if(heap[min_pos]<heap[parent]){
                int temp=heap[min_pos];
                heap[min_pos]=heap[parent];
                heap[parent]=temp;
                temp=tag[min_pos];
                tag[min_pos]=tag[parent];
                tag[parent]=temp;
                if(min_pos*2+1<size){
                    adjust_heap(heap,tag,size,min_pos);
                }
            }
        }
        else if(left_child<size){
            if(heap[left_child]<heap[parent]){
                int temp=heap[left_child];
                heap[left_child]=heap[parent];
                heap[parent]=temp;
                temp=tag[left_child];
                tag[left_child]=tag[parent];
                tag[parent]=temp;
            }
        }
    }
    
    void init_heap(int* heap,int* tag,int size){
        int i=size/2-1;
        for(;i>=0;--i){
            adjust_heap(heap,tag,size,i);
        }
    }
    
    void insert_heap(int* heap,int* tag,int size,int new_val, int new_tag){
        heap[0]=new_val;
        tag[0]=new_tag;
        adjust_heap(heap,tag,size,0);
    }
    
    void pop_heap(int* heap,int* tag,int size){
        heap[0]=heap[size-1];
        tag[0]=tag[size-1];
        adjust_heap(heap,tag,size-1,0);
    }
    
    struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
        if(listsSize<=1){
            return lists[0];
        }
        //malloc and init
        int* heap=(int*)malloc(sizeof(int)*listsSize);
        int* tag=(int*)malloc(sizeof(int)*listsSize);//store the index of a list
        memset(tag,0,sizeof(int)*listsSize);
        int i=0;
        int j=0;
        int heap_size=0;
    
        //put numbers into heap
        for(;i<listsSize;i++){
            if(lists[i]==NULL){
                continue;
            }
            heap[heap_size]=lists[i]->val;
            tag[heap_size++]=i;
        }
        
        //if there is only one non-null list just return it
        if(heap_size<=1){
            free(heap);
            int res=tag[0];
            free(tag);
            return lists[res];
        }
        
        //init a heap
        init_heap(heap,tag,heap_size);
        
        //make the reslist link to the first node
        int first_node=tag[0];
        struct ListNode* resList=lists[first_node];
        struct ListNode* next=resList;
        lists[first_node]=lists[first_node]->next;
        if(lists[first_node])
            insert_heap(heap,tag,heap_size,lists[first_node]->val,first_node);
        else
            pop_heap(heap,tag,heap_size--);
        //start to work
        while(heap_size){
            int t=tag[0];
            next->next=lists[t];
            next=next->next;
            lists[t]=lists[t]->next;
            if(lists[t])
                insert_heap(heap,tag,heap_size,lists[t]->val,t);
            else
                pop_heap(heap,tag,heap_size--);
        }
        free(heap);
        free(tag);
        return resList;
    }
    

Log in to reply
 

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