Share My C code in 13ms, use min-heap.


  • 4
    Y

    In this problem, input is linked lists; divide an conquer works good.

    But if we need to sort arrays or vectors, divide and conquer will spend too much extra space.

    So I think, maybe heap (or loser tree) is a better method.(when K is big enough)

    The time complexity is O(k) + O(nlgk). (divide and conquer is exactly n*lg(k), more comparison times)

    void MIN_HEAP_SORT(struct ListNode **lists, int index_i,int size)
    {
    	int left = index_i*2 + 1;
    	int right= index_i*2 + 2;
    	if(left>=size)
    		return;
    	int min;
    	if(right>=size)
    		min = left;
    	else
    		min = lists[left]->val<lists[right]->val?left:right;
    	if(lists[index_i]->val>lists[min]->val){
    		struct ListNode *temp = lists[index_i];
    		lists[index_i] = lists[min];
    		lists[min] = temp;
    		MIN_HEAP_SORT(lists,min,size);
    	}
    }
    
    void BuildHeap(struct ListNode **lists,int size)
    {
    	for(int i=(size-1)/2;i>=0;--i){
    		MIN_HEAP_SORT(lists,i,size);
    	}
    }
    
    struct ListNode *mergeKLists(struct ListNode *lists[], int k) {
    	if(k==0)
    		return NULL;//1
    	struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    	struct ListNode *int_max = (struct ListNode*)malloc(sizeof(struct ListNode));
    	int_max->val = INT_MAX;
    	int_max->next = NULL;
    	struct ListNode *travel = head;
    	for(int i=0;i<k;++i){
    		if(lists[i]==NULL)
    			lists[i] = int_max;
    	}/*remove those NULL ptr*/
    	BuildHeap(lists,k);
    	while(lists[0]!=int_max){
    		travel->next = lists[0];
    		travel = lists[0];
    		lists[0] = lists[0]->next;
    		if(lists[0]==NULL)
    			lists[0] = int_max;
    		MIN_HEAP_SORT(lists,0,k);
    	}
    	travel->next = NULL;
    	return head->next;
    }
    

    there is an extra head node, an extra INT_MAX node (used to replace NULL ptr)


  • 1
    R

    you mean your 392 ms solution -- I did it in C++ with priority_queue and a comparison function on the pointers and it ran in 420 ms -- so I wanted to check if there was another fast C/C++ solution. I checked yours and a few more -- they all run in around 400ms (-20 ms for C, +20ms for C++)


  • 0
    Y

    Some test cases are added.


  • 0
    K

    I submit my code for merge k sorted list but OJ produce "Last executed input: []" . Can anybody tell me what is it meaning?


  • 0
    S

    an empty list is passed


  • 0
    W

    my idea is just like you, but at first I did not thought the small tips of ListNode max, to reference your code, my solution passed in 9 ms, thank you very much
    '''
    //将当前值调节入
    void adjustTree(struct ListNode** lists, int listSize, int index)
    {
    int resultIndex = 0;
    int leftIndex = index * 2 + 1;
    int rightIndex = index * 2 + 2;

    if(leftIndex >= listSize)
        return;
    
    
    int indexValue = lists[index]->val;
    int leftValue = lists[leftIndex]->val;
    int rightValue = (rightIndex) >= listSize ? INT_MAX : lists[rightIndex]->val;
    
    if(leftValue <= rightValue)
    {
        //此时进行交换
        if(indexValue > leftValue)
        {
            struct ListNode* temp = lists[index];
            lists[index] = lists[leftIndex];
            lists[leftIndex] = temp;
            resultIndex = leftIndex;
            adjustTree(lists,listSize,resultIndex);
        }
    
    } else
    {
        if(indexValue > rightValue)
        {
            struct ListNode* temp = lists[index];
            lists[index] = lists[rightIndex];
            lists[rightIndex] = temp;
            resultIndex = rightIndex;
            adjustTree(lists,listSize,resultIndex);
        }
    }
    

    }

    //建立小顶堆的过程
    void buildTree(struct ListNode** lists, int listSize)
    {
    //建树的过程要从下标 (n-1)/2 处开始
    int begin = (listSize-1) / 2;
    for(int index = begin; index >= 0; index--)
    adjustTree(lists, listSize, index);

    }

    //此处理解lists应该认为是所有的list的头的合集
    struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
    {

    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* max = (struct ListNode*)malloc(sizeof(struct ListNode));
    max->val = INT_MAX;
    max->next = NULL;
    
    if(listsSize == 0)
        return NULL;
    
    //设置一个最大的堆,用于替代链表最后的空值.
    for(int i = 0; i < listsSize; i++)
    {
        if(lists[i] == NULL)
            lists[i] = max;
    }
    //以k个头结点建立小顶堆
    buildTree(lists, listsSize);
    struct ListNode* cur = head;
    
    
    while (lists[0] != max)
    {
        cur->next = lists[0];
        cur = lists[0];
        lists[0] = lists[0]->next;
    
        if(lists[0] == NULL)
            lists[0] = max;
    
        adjustTree(lists,listsSize,0);
    }
    cur->next = NULL;
    
    return head->next;
    

    }
    '''


Log in to reply
 

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