【原创】leetCodeOj --- Merge k Sorted Lists 解题报告

题目地址:

https://oj.leetcode.com/problems/merge-k-sorted-lists/

题目内容:

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

方法:

用最小堆来做就可以了。第一轮将链表所有头结点插入堆中,当堆非空时,弹出一个结点加入输出链表,若该结点有后继结点,则后继结点入堆。

复杂度分析:

设有k个链表,每个链表有n个结点。

则堆的大小最多为k。

每个结点都要入一次堆并出一次堆,入堆的复杂度为lgk,出堆时为了维护堆的性质复杂度也是lgk

一共有k * n个结点

所以,总的复杂度为O(k * n * lgk)

如果简单粗暴直接堆排序,那么堆的大小就是k * n,入堆出堆的复杂度就是lg(k * n),要大不少。

如果直接按归并排序那样简单粗暴的归并,那么每轮中获得获胜结点的复杂度是k,由于每轮只产生一个获胜结点,所以一共有 k * n轮,那么复杂度就是O(k * k * n)

AC代码:(直接手写heap,免得重载运算符)

class Solution {

    class MergeHeap
{
public:
MergeHeap()
{
heap.push_back(NULL);
}
bool isEmpty()
{
return heap.size() <= ; // 0号元素永远为NULL
}
void insert(ListNode *tmp)
{
if (tmp == NULL)
return;
heap.push_back(tmp);
mergeInsert();
}
ListNode *pop()
{
if (this->isEmpty())
return NULL;
int last = heap.size() - ;
ListNode *tmp = heap[];
heap[] = heap[last];
heap.pop_back();
if (!this->isEmpty())
mergeDelete();
return tmp;
} private:
vector<ListNode *> heap;
void mergeDelete(int start)
{
int last = heap.size() - ;
ListNode *tmp = heap[start];
int lchild = start * ;
int rchild = start * + ;
int target = ; // marked win sub-tree
if (lchild <= last && rchild <= last)
{
target = heap[rchild]->val > heap[lchild]->val ? lchild : rchild; }
else if (lchild <= last)
{
target = lchild;
}
else if (rchild <= last)
target = rchild;
if (target)
{
if (heap[target]->val < heap[start]->val)
{
heap[start] = heap[target];
heap[target] = tmp;
mergeDelete(target);
}
} }
void mergeInsert()
{
int last = heap.size() - ;
int pare = last / ;
while (pare != )
{
if (heap[pare]->val > heap[last]->val)
{
ListNode *tmp = heap[pare];
heap[pare] = heap[last];
heap[last] = tmp;
}
else
break;
last = pare;
pare /= ;
}
}
};
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
MergeHeap myheap;
int len = lists.size();
if (!len)
return NULL;
for (int i = ;i < len;i++)
myheap.insert(lists[i]);
ListNode *head = NULL;
ListNode *tmp = NULL;
ListNode *tail = NULL;
while (!myheap.isEmpty())
{
tmp = myheap.pop();
if (!head) // init output list.
{
head = tmp;
tail = tmp;
}
else
{
tail->next = tmp;
tail = tmp;
}
if (tmp->next)
{
myheap.insert(tmp->next);
} }
return head;
}
};
上一篇:poj3067


下一篇:opensips编译安装时可能遇到的问题