A Fast Java solution using PriorityQueue. TimeComplexity o(n*k*lg(k))


  • 2
    2

    Assuming there are n lists, and average length of lists is k.

    • Time Complexity : o(nklg(k))

    • Space Complexity o(k)

      public class Solution {

       class ListNodeComparator implements Comparator<ListNode>
       {
           public int compare(ListNode o1, ListNode o2)
           {
               if (o1.val < o2.val)
                   return -1;
               else if (o1.val == o2.val)
                   return 0;
               else
                   return 1;
           }
       }
       
       public ListNode mergeKLists(List<ListNode> lists) {
           if (lists.size() == 0) //!! if lists.size() == 0, the new PriorityQueue(size, Comparator()) would throw java.lang.iLegalStatement. because size should > 0
               return null;
           PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(), new ListNodeComparator());   
           ListNode dummy = new ListNode(-1);
           dummy.next = null;
           ListNode tail = dummy;
           for (ListNode ln    :   lists)
               if (ln != null)                 //!! it is possible that list contains null
                   pq.add(ln);
           while (pq.size() > 0)
           {
               ListNode node = pq.poll();
               if (node.next != null)
                   pq.add(node.next);
               tail.next = node;
               tail = node;
           }
           tail.next = null;
           return dummy.next;
       }
      

      }


  • 0
    B

    The time complexity should be O(NlogK). As each 'add' to priority queue is O(logk) and it takes N times of 'add'.


  • 0
    2

    Nice to have your reply;-)

    It actually has n*k ListNode, (n lists, and each k node in each list), and each node should be added into the priorityqueue, so the time complexity should be n * k * lg(k)


  • 0
    B

    Sorry. I missed your assumption in the beginning. . Based on your assumption as n lists and average length is k. It is totally correct.


  • 0
    2

    Yep, if we assume the N means number of all nodes, Time complexity is O(N*log(k)) ;-)


  • 0
    W

    yeah, it is cool! I followed your code and got accepted.
    the time complexity is a definitely O(N * logK). (N means the number of all nodes)
    the option of add or poll cost logK when use min heap or priorityQueye which size is K.
    and for every listnode you need add it to the queue and pol it out


  • 0
    H

    The min heap contains at most n elements at any time. To initially construct it takes nlogn. Each insertion take logn. There are kn elements. So totally the complexity should be nlogn + kn*logn = knlogn?


  • 0
    R

    I totally agree with you, it should be knlogn


  • 0
    C

    I think O(knlogn) is correct time complexity!


Log in to reply
 

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