Is there any solution whose time complexity is kn?


  • 0
    A

    I use the method below to solve this problem:

    I set a loop. In every loop, I try to find out the smallest head node in k lists, then I move this node to the list which would be returned as the result.

    here is my code:

    ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode* res = NULL;
    ListNode* head = NULL;
    while (1){
    bool flag = false;
    int minIndex;
    int minValue = 0x7fffffff;
    for (int i = 0; i < lists.size(); i++) {
    if (lists[i]) flag = true;
    else continue;
    if (lists[i]->val < minValue) {
    minIndex = i;
    minValue = lists[i]->val;
    }
    }
    if (flag) {
    if (!res) {
    res = head = lists[minIndex];
    lists[minIndex] = lists[minIndex]->next;
    continue;
    }
    res->next = lists[minIndex];
    res = res->next;
    lists[minIndex] = lists[minIndex]->next;
    continue;
    }
    break;
    }
    return head;
    }

    Cause this method takes k*n times to compare,does that means its time complexity is kn ?
    I'm really confused why this method turns out to be very Inefficient. Its run time is 538ms. :(

    Hope somebody can help explain this problem.

    Thank you !!


  • 0
    A

    Sorry, the code is as below:

    ListNode* mergeKLists(vector<ListNode*>& lists) {
    	ListNode* res = NULL;
    	ListNode* head = NULL;
    	while (1){
    		bool flag = false;
    		int minIndex;
    		int minValue = 0x7fffffff;
    		for (int i = 0; i < lists.size(); i++) {
    			if (lists[i]) flag = true;
    			else continue;
    			if (lists[i]->val < minValue) {
    				minIndex = i;
    				minValue = lists[i]->val;
    			}
    		}
    		if (flag) {
    			if (!res) {
    				res  = head = lists[minIndex];
    				lists[minIndex] = lists[minIndex]->next;
    				continue;
    			}
    			res->next = lists[minIndex];
    			res = res->next;
    			lists[minIndex] = lists[minIndex]->next;
    			continue;
    		}
    		break;
    	}
    	return head;
    }

  • 0
    A

    O(kn) is slow enough :) the optimal would be O(nLog k )


  • 0
    A

    @aygul Thank you, aygul.
    Could you tell me how to solve this problem in just O(nlogk)? :)


  • 0
    A

    @angiehoo see my latest topic in the problem discussion.


  • 0
    A

    @aygul great! thank you!


Log in to reply
 

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