合并K排序链表

Question

具体来说，如何提高算法的时间复杂度(目前是O(listLength * numberOfLists))？它只超过了5%被接受的LeetCode解决方案，这让我感到惊讶。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private void advance(final ListNode[] listNodes, final int index) {
        listNodes[index] = listNodes[index].next;
    }

    public ListNode mergeKLists(final ListNode[] listNodes) {
        ListNode sortedListHead = null;
        ListNode sortedListNode = null;

        int associatedIndex;

        do {            
            int minValue = Integer.MAX_VALUE;
            associatedIndex = -1;

            for (int listIndex = 0; listIndex < listNodes.length; listIndex++) {
                final ListNode listNode = listNodes[listIndex];

                if (listNode != null && listNode.val < minValue) {                
                    minValue = listNode.val;
                    associatedIndex = listIndex;
                }
            }

            // An associated index of -1 indicates no more values left in any of the given lists
            if (associatedIndex != -1) {
                if (sortedListNode == null) {
                    sortedListNode = new ListNode(minValue);
                    sortedListHead = sortedListNode;
                }
                else {
                    sortedListNode.next = new ListNode(minValue);
                    sortedListNode = sortedListNode.next;
                }

                advance(listNodes, associatedIndex);
            }
        }
        while (associatedIndex != -1);

        return sortedListHead;
    }
}

请注意，除了ListNode之外，已经提供了D3类，我编写的唯一代码是在mergeKLists中。

Answer 1

时间复杂度是O(\text{listLength} * \text{numberOfLists}^2)，因为检查哪个节点最小？每次迭代都查看每个列表中的一个元素(因此每个迭代的复杂性都是O(\text{numberOfLists})，还有\text{listLength} * \text{numberOfLists}迭代。

您可以通过使用每次迭代中签入的O(\text{listLength} * \text{numberOfLists} * \log(\text{numberOfLists}))元素的排序列表来获得ListNode，而不是使用未排序的数组listNodes。让我们把这个列表称为sortedNodes。您可以避免每次迭代检查sortedNodes的每个元素，因为您知道第一个元素是最小的，并且一旦将第一个值放入合并列表并提前节点--执行二进制搜索，在第一个元素的值更改后决定在哪里移动它。(如果到达null，也可以将其移除。)

Answer 2

评论建议您可以获得\mathcal{O}(n\log{m})，其中n是所有列表中元素的总数，m是列表的数量。你怎么能得到\mathcal{O}(n\log{m})？答案是维护一个已排序列表的容器。两个可能的容器是SortedSet (例如TreeSet)或PriorityQueue (用堆实现)。两者都有\mathcal{O}(\log{m})插入和删除。您将执行\mathcal{O}(n)插入和删除(即对列表中的每个元素执行一个)。总体上是\mathcal{O}(n\log{m})。

您当前的代码是\mathcal{O}(n\cdot m)，因此\mathcal{O}(n\log{m})将是渐进的改进。

考虑一下

    public ListNode mergeKLists(final ListNode[] listNodes) {
        PriorityQueue lists = new PriorityQueue<>(Arrays.asList(listNodes));

        // create a dummy head so as to have the same logic for the first node as the others
        ListNode head = new ListNode(0);
        ListNode current = head;
        for (ListNode node = lists.poll(); node != null; node = lists.poll()) {
            current.next = new ListNode(node.val);
            current = current.next;

            if (node.next != null) {
                lists.add(node.next);
            }
        }

        return head.next;
    }

for循环将运行n次数(对列表中的每个元素运行一次)。poll和add操作都将占用\mathcal{O}(\log{m})时间。所以总体来说，\mathcal{O}(n\log{m})。PriorityQueue的创建将采用\mathcal{O}(m\log{m})，所以这就是\mathcal{O}((n + m)\log{m})。如果我们假设没有一个列表是空的，那么m <= n，所以\mathcal{O}(n\log{m})。

如果要插入列表的第一个元素，我们就可以避免在每次迭代中检查return head.next的问题。head本身并不是我们正在创建的列表的一部分，只是一个占位符。另一种选择是在列表之外创建第一个元素。

此代码假定listNodes中没有一个条目为null。如果可以的话，你需要另外检查那个案子。它还假设ListNode与val是可比较的。如果不是，则必须将一个Comparator传递给PriorityQueue构造函数以实现该行为。SortedSet版本是相似的，但也有相同的限制。

对于Comparator和容量集，空检查，没有虚拟头，并且current声明为循环声明的一部分(为了更好地限定范围，因为current不在循环之外使用)：

    public ListNode mergeKLists(final ListNode[] listNodes) {
        PriorityQueue lists = new PriorityQueue<>(listNodes.length,
                new Comparator() {

                    int compare(ListNode a, ListNode b) {
                        return Integer.compare(a.val, b.val);
                    }

                });

        for (ListNode node : listNodes) {
            if (node != null) {
                lists.add(node);
            }
        }

        if (lists.isEmpty()) {
            return null;
        }

        ListNode head = new ListNode(lists.poll().val);
        for (ListNode node = lists.poll(), current = head; node != null; node = lists.poll()) {
            current.next = new ListNode(node.val);
            current = current.next;

            if (node.next != null) {
                lists.add(node.next);
            }
        }  

        return head;
    }

我认为假人的头脑实际上更容易，但你可能会发现这种形式更易读。

我还没有测试过这个，所以要小心语法错误等等。