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 :)。