TLE by using java PriorityQueue


  • 0
    K

    the code is here:

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        Queue<ListNode> queue = new PriorityQueue<>(lists.length,new Comparator<ListNode>(){
    		@Override
    		public int compare(ListNode l1, ListNode l2) {
    			return l1.val - l2.val;
    		}
        	
        });
        ListNode head = new ListNode(0);
        ListNode p = head;
        for(ListNode node : lists) {
            if(node != null)
        	    queue.offer(node);
        }
        while(!queue.isEmpty()) {
        	ListNode node = queue.poll();
        	p.next = node;
        	if(node.next != null)
        		queue.offer(node.next);
        	p = p.next;
        }
        return head.next;
    }
    

    The result is TLE, but if I change the "compare" method like this:

    public int compare(ListNode l1, ListNode l2) {
          if (l1.val < l2.val)
                return -1;
          else if (l1.val == l2.val)
                return 0;
          else
                return 1;
    }
    

    the result is AC, can anybody tell me why?


  • 0
    H

    Because your original comparator is wrong. It will overflow. Imagine that you compare Integer.MAX_VALUE with -1 with your comparator. It will give a negative value.


Log in to reply
 

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