What's the difference between merge lists one by one or using divide and conquer


  • 0
    B

    Since they both require k - 1 times merge, then why using divide-conquer is better than merge list from first and one by one?

    Solution 1 - Merge one by one (TLE):

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
    
        int i = 1;
        ListNode newList = lists[0];
        ListNode p = newList;
    
        while (i < lists.length - 1) {
            newList = mergeLists(newList, lists[i]);
            i++;
        }
    
        return lists[i];
    }
    

    Solution 2 - 3ms:

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeKLists(lists, 0, lists.length - 1);
    }
    
    public ListNode mergeKLists(ListNode[] lists, int i, int j) {
        if (i == j) {
            return lists[i];
        }
        
        ListNode a = lists[i];
        ListNode b = lists[j];
        if (j - i >= 2) {
            int middle = i + (j - i) / 2;
            a = mergeKLists(lists, i, middle);
            if (middle + 1 != j) {
                b = mergeKLists(lists, middle + 1, j);
            }
        }
        return mergeLists(a,b);
    }

  • 0
    J

    Consider the worst case that the lists are sorted in length descending order. If you use the merge-one-by-one solution, you are dealing with the longest list every time ( (n - 1) times to be accurate )! But what if you use the merge one? You only deal with it log(n) times! That's an improve there.


Log in to reply
 

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