c++ - 合并 k 个排序列表超出时间限制(leetcode)

Question

merge-k-sorted-lists

合并 k 个已排序的链表并将其作为一个已排序的列表返回。分析并描述其复杂性。

我的代码:

    ListNode *mergeTwoLists(ListNode *p1, ListNode *p2) {
    ListNode dummy(-1);
    ListNode *head = &dummy;
    while(p1 != nullptr && p2 != nullptr) {
        if (p1->val < p2->val) {
            head->next = p1;
            head = head->next;
            p1 = p1->next;
        } else {
            head->next = p2;
            head = head->next;
            p2 = p2->next;
        }
    }
    if (p1 != nullptr) {
        head->next = p1;
    }
    if (p2 != nullptr) {
        head->next = p2;
    }
    //head->next = nullptr;
    return dummy.next;
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
    if (lists.size() == 0) return nullptr;
    if (lists.size() == 1) return lists[0];
    ListNode *p1, *p2, *p;
    while (lists.size() > 1) {
        p1 = lists.back();
        lists.pop_back();
        p2 = lists.back();
        lists.pop_back();
        p = mergeTwoLists(p1, p2);
        lists.push_back(p);
    }
    return lists[0];
}

我总是收到超出时间限制的消息。我应该如何更改程序？

Answer 1

您正在做的事情具有复杂性 O(nk^2)，其中 n 是每个数组的大小。您一次合并两个列表。为什么 ？您合并前两个列表需要 2n 操作，前两个合并的大小也是 2n。现在将它与第三个合并，数组大小变为 3n 并且完成了 3n 操作，因此操作总数为 2n+3n+....kn (等差级数)是 O(nk^2)。而是采用优先级队列(最小堆)插入所有 k 列表的第一个元素。现在每次从优先级队列中取出最小的元素(将其放入您的新列表中)，将其从优先级队列中删除并插入该元素所属列表的下一个元素。由于所有元素都从优先级队列中插入和删除一次，总共有 nk 个元素，因此复杂度为 O(nklog(k))。 (删除/插入时间)优先级队列为 O(log(number_of_elements_in_queue))。并且队列中任何时刻最多有k个元素。
如需更详细的解释和代码，请查看此处:Merging k sorted lists .我认为这足以在 leetcode 上获得 AC :)。