请教各位大牛一个K-way merge 的问题# JobHunting - 待字闺中
d*o
1 楼
上面那个targus messenger，早上7：00am有人在fw上发帖，价格是21.99，结果一直到
下午都还是这个价格。lava贴出后两小时价格就成了64了。
下午都还是这个价格。lava贴出后两小时价格就成了64了。
c*7
2 楼
原题是leetcode上的merge k sorted lists
http://discuss.leetcode.com/questions/204/merge-k-sorted-lists
这个题有好几种解法，比如divide and conquer, priority queue.
我写了个priority queue的。我的问题是， 如果现在要做 merge k sorted
array,怎样来设计这个priority queue才能最简单有效呢？
附上 merge-k-sorted-lists的代码
public static ListNode mergeKLists_priorityQueue(ArrayList kLists)
{
// border case
if(kLists.size()==0) return null;
if(kLists.size()==1) return kLists.get(0);
// create a Comparator based on the node's val for the PriorityQueue
Comparator nodeComparator = new Comparator(){
@Override
public int compare(ListNode node1, ListNode node2) {
// TODO Auto-generated method stub
if (node1.val < node2.val)
return -1;
else if (node1.val > node2.val)
return 1;
else// two node's val are equal
return 0;
}
};
// create a priority queue
PriorityQueue priQueue = new PriorityQueue(
kLists.size(),nodeComparator);
// initialize the priQueue with the first node of each list
for(int i = 0; i < kLists.size(); i++){
// if it is not null node, add it to the PriorityQueue
if (kLists.get(i)!=null)
priQueue.add(kLists.get(i));
}
// create a dummy head
ListNode dummyHead = new ListNode(-1);
// the indexing node of the merged list
ListNode curNode = dummyHead;
// keep choose the top item from the priority queue,
// and add it to the merged list
while(!priQueue.isEmpty()){
// get the top item of the priority queue,
// which will be the node with min val
ListNode minNode = priQueue.poll();
// add the node to the merged list
curNode.next = minNode;
// update curNode
curNode=curNode.next;
// get the next node of the minNode
minNode = minNode.next;
// if it is NOT, i.e., the list does not hit the end,
// add its next node to the priority queue
if (minNode!=null){
priQueue.add(minNode);
}
}
return dummyHead.next;
}
http://discuss.leetcode.com/questions/204/merge-k-sorted-lists
这个题有好几种解法，比如divide and conquer, priority queue.
我写了个priority queue的。我的问题是， 如果现在要做 merge k sorted
array,怎样来设计这个priority queue才能最简单有效呢？
附上 merge-k-sorted-lists的代码
public static ListNode mergeKLists_priorityQueue(ArrayList
{
// border case
if(kLists.size()==0) return null;
if(kLists.size()==1) return kLists.get(0);
// create a Comparator based on the node's val for the PriorityQueue
Comparator
@Override
public int compare(ListNode node1, ListNode node2) {
// TODO Auto-generated method stub
if (node1.val < node2.val)
return -1;
else if (node1.val > node2.val)
return 1;
else// two node's val are equal
return 0;
}
};
// create a priority queue
PriorityQueue
kLists.size(),nodeComparator);
// initialize the priQueue with the first node of each list
for(int i = 0; i < kLists.size(); i++){
// if it is not null node, add it to the PriorityQueue
if (kLists.get(i)!=null)
priQueue.add(kLists.get(i));
}
// create a dummy head
ListNode dummyHead = new ListNode(-1);
// the indexing node of the merged list
ListNode curNode = dummyHead;
// keep choose the top item from the priority queue,
// and add it to the merged list
while(!priQueue.isEmpty()){
// get the top item of the priority queue,
// which will be the node with min val
ListNode minNode = priQueue.poll();
// add the node to the merged list
curNode.next = minNode;
// update curNode
curNode=curNode.next;
// get the next node of the minNode
minNode = minNode.next;
// if it is NOT, i.e., the list does not hit the end,
// add its next node to the priority queue
if (minNode!=null){
priQueue.add(minNode);
}
}
return dummyHead.next;
}
n*n
3 楼
辣娃太hot了
【在 d*******o 的大作中提到】
: 上面那个targus messenger，早上7：00am有人在fw上发帖，价格是21.99，结果一直到
: 下午都还是这个价格。lava贴出后两小时价格就成了64了。
【在 d*******o 的大作中提到】
: 上面那个targus messenger，早上7：00am有人在fw上发帖，价格是21.99，结果一直到
: 下午都还是这个价格。lava贴出后两小时价格就成了64了。
d*i
4 楼
我不是大牛，呵呵，错了别见怪。
如果是c++的话，可以用p_queue存储array的iterator吧，然后写个compare function
就行了吧
如果是c++的话，可以用p_queue存储array的iterator吧，然后写个compare function
就行了吧
j*1
5 楼
错过了
w*x
6 楼
不用堆得版本：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *mergeKLists(vector &lists) {
ListNode* pHead = NULL;
ListNode* pIter = NULL;
while (true)
{
int p = -1;
for (int i = 0; i < lists.size(); i++)
{
if (lists[i] != NULL)
{
if (p < 0 || lists[i]->val < lists[p]->val)
p = i;
}
}
if (p < 0) break;
if (pHead == NULL)
{
pHead = lists[p];
pIter = lists[p];
}
else
{
pIter->next = lists[p];
pIter = pIter->next;
}
lists[p] = lists[p]->next;
}
return pHead;
}
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *mergeKLists(vector
ListNode* pHead = NULL;
ListNode* pIter = NULL;
while (true)
{
int p = -1;
for (int i = 0; i < lists.size(); i++)
{
if (lists[i] != NULL)
{
if (p < 0 || lists[i]->val < lists[p]->val)
p = i;
}
}
if (p < 0) break;
if (pHead == NULL)
{
pHead = lists[p];
pIter = lists[p];
}
else
{
pIter->next = lists[p];
pIter = pIter->next;
}
lists[p] = lists[p]->next;
}
return pHead;
}
a*e
7 楼
这个包很有意思吗？
【在 d*******o 的大作中提到】
: 上面那个targus messenger，早上7：00am有人在fw上发帖，价格是21.99，结果一直到
: 下午都还是这个价格。lava贴出后两小时价格就成了64了。
【在 d*******o 的大作中提到】
: 上面那个targus messenger，早上7：00am有人在fw上发帖，价格是21.99，结果一直到
: 下午都还是这个价格。lava贴出后两小时价格就成了64了。
b*n
8 楼
我也刚好写了一个，跟你一个思路，有空了再写个用heap的。
ListNode *mergeKLists(vector &lists) {
ListNode res = ListNode(0);
ListNode *curLN = &res;
while(true) {
int minV = INT_MAX;
int minI;
for(int i=0; i
minV = lists[i]->val;
minI = i;
}
}
if (minV == INT_MAX) break;
curLN->next = lists[minI];
curLN = curLN->next;
lists[minI] = lists[minI]->next;
}
return res.next;
}
【在 w****x 的大作中提到】
: 不用堆得版本：
: struct ListNode {
: int val;
: ListNode *next;
: ListNode(int x) : val(x), next(NULL) {}
: };
: ListNode *mergeKLists(vector &lists) {
: ListNode* pHead = NULL;
: ListNode* pIter = NULL;
: while (true)
ListNode *mergeKLists(vector
ListNode res = ListNode(0);
ListNode *curLN = &res;
while(true) {
int minV = INT_MAX;
int minI;
for(int i=0; i
minV = lists[i]->val;
minI = i;
}
}
if (minV == INT_MAX) break;
curLN->next = lists[minI];
curLN = curLN->next;
lists[minI] = lists[minI]->next;
}
return res.next;
}
【在 w****x 的大作中提到】
: 不用堆得版本：
: struct ListNode {
: int val;
: ListNode *next;
: ListNode(int x) : val(x), next(NULL) {}
: };
: ListNode *mergeKLists(vector
: ListNode* pHead = NULL;
: ListNode* pIter = NULL;
: while (true)
f*g
9 楼
中毒了,哈哈
p*2
10 楼
这个貌似复杂度高吧？
【在 b*****n 的大作中提到】
: 我也刚好写了一个，跟你一个思路，有空了再写个用heap的。
: ListNode *mergeKLists(vector
: ListNode res = ListNode(0);
: ListNode *curLN = &res;
: while(true) {
: int minV = INT_MAX;
: int minI;
: for(int i=0; i
: minV = lists[i]->val;
d*o
11 楼
really? 那我就拒收包裹了
【在 f****g 的大作中提到】
: 中毒了,哈哈
【在 f****g 的大作中提到】
: 中毒了,哈哈
c*t
12 楼
好像是O(m*n)? 用heap是 O(nlog(m))吧
【在 p*****2 的大作中提到】
:
: 这个貌似复杂度高吧？
【在 p*****2 的大作中提到】
:
: 这个貌似复杂度高吧？
c*a
13 楼
我的用堆
public ListNode mergeKLists(ArrayList lists) {
Comparator mycomp = new Comparator(){
@Override
public int compare(ListNode a, ListNode b){
if(a.val
else return 1;
}
};
if(lists.size()==0) return null;
PriorityQueue heap = new PriorityQueue(lists.
size(), mycomp);
for(ListNode node: lists){
if(node!=null)
heap.add(node);
}
ListNode head= new ListNode(0);
ListNode prev = head;
while(heap.size()>0){
ListNode curr = heap.poll();
prev.next = curr;
prev = curr;
curr = curr.next;
if(curr!=null)
heap.add(curr);
}
return head.next;
}
public ListNode mergeKLists(ArrayList
Comparator
@Override
public int compare(ListNode a, ListNode b){
if(a.val
else return 1;
}
};
if(lists.size()==0) return null;
PriorityQueue
size(), mycomp);
for(ListNode node: lists){
if(node!=null)
heap.add(node);
}
ListNode head= new ListNode(0);
ListNode prev = head;
while(heap.size()>0){
ListNode curr = heap.poll();
prev.next = curr;
prev = curr;
curr = curr.next;
if(curr!=null)
heap.add(curr);
}
return head.next;
}
w*x
14 楼
我那个算法是nlogn吗？
【在 c********t 的大作中提到】
: 好像是O(m*n)? 用heap是 O(nlog(m))吧
b*n
15 楼
是的，稍后再写个heap的，以前写过heap的class。现在为了赶进度，就先把它放到我
的Todo list里了。目前进度55/125 :)
【在 p*****2 的大作中提到】
:
: 这个貌似复杂度高吧？
的Todo list里了。目前进度55/125 :)
【在 p*****2 的大作中提到】
:
: 这个貌似复杂度高吧？
b*n
16 楼
是的，骑士说的没错
【在 c********t 的大作中提到】
: 好像是O(m*n)? 用heap是 O(nlog(m))吧
【在 c********t 的大作中提到】
: 好像是O(m*n)? 用heap是 O(nlog(m))吧
b*n
17 楼
你那个和我的几乎是一模一样的 :)
【在 w****x 的大作中提到】
:
: 我那个算法是nlogn吗？
【在 w****x 的大作中提到】
:
: 我那个算法是nlogn吗？
w*x
18 楼
n代表list个数m代表平均节点数吧， 那怎么可能是nlogm, 每个节点都不走一边？
应该是m*nlogn吧， 我那个也是m*nlogn， 一个复杂度
【在 b*****n 的大作中提到】
: 你那个和我的几乎是一模一样的 :)
b*h
19 楼
你的找最值是用 loop O(K) 的，如果用优先队列或者 set 就是 O(logK) 啦 其他都是
一样的
【在 w****x 的大作中提到】
:
: n代表list个数m代表平均节点数吧， 那怎么可能是nlogm, 每个节点都不走一边？
: 应该是m*nlogn吧， 我那个也是m*nlogn， 一个复杂度
一样的
【在 w****x 的大作中提到】
:
: n代表list个数m代表平均节点数吧， 那怎么可能是nlogm, 每个节点都不走一边？
: 应该是m*nlogn吧， 我那个也是m*nlogn， 一个复杂度
w*x
20 楼
不是吧，我的是log级的，你在仔细想想
【在 b*********h 的大作中提到】
: 你的找最值是用 loop O(K) 的，如果用优先队列或者 set 就是 O(logK) 啦 其他都是
: 一样的
b*h
21 楼
看大家都用优先队列，贴一个 set 的吧 呵呵，用 C++ 的表示声明 priority queue
打字太多。。。继续说 C++ 的 priority queue 又不支持 decrease key，喜欢用 set
当 priority queue 。。。
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
multiset S;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i]) {
S.insert(lists[i]);
}
}
ListNode* head = 0;
ListNode* tail = 0;
while (!S.empty()) {
ListNode* node = *S.begin();
S.erase(S.begin());
if (!head) {
head = tail = node;
}
else {
tail = tail->next = node;
}
if (node->next) {
S.insert(node->next);
}
}
return head;
}
struct comparator: public binary_function {
bool operator() (const ListNode* a, const ListNode* b) {
return a->val < b->val;
}
};
};
打字太多。。。继续说 C++ 的 priority queue 又不支持 decrease key，喜欢用 set
当 priority queue 。。。
class Solution {
public:
ListNode *mergeKLists(vector
multiset
for (int i = 0; i < lists.size(); ++i) {
if (lists[i]) {
S.insert(lists[i]);
}
}
ListNode* head = 0;
ListNode* tail = 0;
while (!S.empty()) {
ListNode* node = *S.begin();
S.erase(S.begin());
if (!head) {
head = tail = node;
}
else {
tail = tail->next = node;
}
if (node->next) {
S.insert(node->next);
}
}
return head;
}
struct comparator: public binary_function
bool operator() (const ListNode* a, const ListNode* b) {
return a->val < b->val;
}
};
};
b*h
22 楼
啊 真的没明白。。。
【在 w****x 的大作中提到】
:
: 不是吧，我的是log级的，你在仔细想想
【在 w****x 的大作中提到】
:
: 不是吧，我的是log级的，你在仔细想想
c*t
23 楼
你说得对，如果按你说的n代表list个数m代表平均节点数吧，是m*n*log(n), 但是你的
codes找min用的是n，不是logn啊，你的复杂度难道不是m*n*n吗？
【在 w****x 的大作中提到】
:
: 不是吧，我的是log级的，你在仔细想想
codes找min用的是n，不是logn啊，你的复杂度难道不是m*n*n吗？
【在 w****x 的大作中提到】
:
: 不是吧，我的是log级的，你在仔细想想
w*x
24 楼
我每次新合并的都丢到队尾了，效果相当于
1 2 3 4 5 6 7 8
=> 12 34 56 79
=> 1234 5678
=> 12345678
logn层
【在 b*********h 的大作中提到】
: 啊 真的没明白。。。
b*h
25 楼
啊？还是没明白怎么合的。。。
要不换个长点的 k 个 lists，比如
1 3 5 7
2 3 4 6
3 5 7 9
可以解释一下怎么合的？
【在 w****x 的大作中提到】
:
: 我每次新合并的都丢到队尾了，效果相当于
: 1 2 3 4 5 6 7 8
: => 12 34 56 79
: => 1234 5678
: => 12345678
: logn层
要不换个长点的 k 个 lists，比如
1 3 5 7
2 3 4 6
3 5 7 9
可以解释一下怎么合的？
【在 w****x 的大作中提到】
:
: 我每次新合并的都丢到队尾了，效果相当于
: 1 2 3 4 5 6 7 8
: => 12 34 56 79
: => 1234 5678
: => 12345678
: logn层
w*x
26 楼
我举得例子里1 2 3 4 5 6 7 8 代表8条list,
12代表原list 1和2 合并的长list
12345678代表最终结果
【在 b*********h 的大作中提到】
: 啊？还是没明白怎么合的。。。
: 要不换个长点的 k 个 lists，比如
: 1 3 5 7
: 2 3 4 6
: 3 5 7 9
: 可以解释一下怎么合的？
b*h
27 楼
那个 loop 不是每次找到一个长 list 的 head 然后接到结果的队尾吗。。。
看程序每次 while 只能消除所有 lists 中的一个元素
没明白 1 2 是怎么一下合起来的
【在 w****x 的大作中提到】
:
: 我举得例子里1 2 3 4 5 6 7 8 代表8条list,
: 12代表原list 1和2 合并的长list
: 12345678代表最终结果
看程序每次 while 只能消除所有 lists 中的一个元素
没明白 1 2 是怎么一下合起来的
【在 w****x 的大作中提到】
:
: 我举得例子里1 2 3 4 5 6 7 8 代表8条list,
: 12代表原list 1和2 合并的长list
: 12345678代表最终结果
w*x
28 楼
1和2在loop的第一次就合起来了啊
比如一开始是1,2,3,4,5,6,7,8
第一个while以后:
1:
3,4,5,6,7,8,12
2:
5,6,7,8,12,34
3:
7,8,12,34,56
4:
12,34,56,78
5:
56,78,1234
6:
1234,5678
7:
12345678 ==> return
1->4 => m*n个
4->6 => m*n个
6->7 => m*n个
一共logn个m*n
复杂度为m*nlogn 这里n为8
【在 b*********h 的大作中提到】
: 那个 loop 不是每次找到一个长 list 的 head 然后接到结果的队尾吗。。。
: 看程序每次 while 只能消除所有 lists 中的一个元素
: 没明白 1 2 是怎么一下合起来的
b*h
29 楼
比如 3 个 lists 吧
[1, 3, 5]
[2, 4, 6]
[3, 3, 3]
那个程序第一次 loop 就把 [1, 3, 5] 和 [2, 4, 6] 合起来了？
【在 w****x 的大作中提到】
:
: 1和2在loop的第一次就合起来了啊
: 比如一开始是1,2,3,4,5,6,7,8
: 第一个while以后:
: 1:
: 3,4,5,6,7,8,12
: 2:
: 5,6,7,8,12,34
: 3:
: 7,8,12,34,56
[1, 3, 5]
[2, 4, 6]
[3, 3, 3]
那个程序第一次 loop 就把 [1, 3, 5] 和 [2, 4, 6] 合起来了？
【在 w****x 的大作中提到】
:
: 1和2在loop的第一次就合起来了啊
: 比如一开始是1,2,3,4,5,6,7,8
: 第一个while以后:
: 1:
: 3,4,5,6,7,8,12
: 2:
: 5,6,7,8,12,34
: 3:
: 7,8,12,34,56
l*b
30 楼
Divide & Conquor的办法，有点长
ListNode *mergeKLists(vector &lists) {
if(lists.empty())
return 0;
int n = lists.size();
while(n > 1) {
int i;
for(i = 0; i < n/2; ++i)
lists[i] = mergeTwoList(lists[2*i], lists[2*i+1]);
if(n % 2) {
lists[i] = lists[n-1];
n = n/2 + 1;
} else
n = n/2;
}
return lists[0];
}
ListNode *mergeTwoList(ListNode *s, ListNode *t) {
ListNode *h, **c = &h;
while(s && t) {
if(s->val < t->val) {
*c = s;
s = s->next;
} else {
*c = t;
t = t->next;
}
c = &(*c)->next;
}
if(s)
*c = s;
else
*c = t;
return h;
}
ListNode *mergeKLists(vector
if(lists.empty())
return 0;
int n = lists.size();
while(n > 1) {
int i;
for(i = 0; i < n/2; ++i)
lists[i] = mergeTwoList(lists[2*i], lists[2*i+1]);
if(n % 2) {
lists[i] = lists[n-1];
n = n/2 + 1;
} else
n = n/2;
}
return lists[0];
}
ListNode *mergeTwoList(ListNode *s, ListNode *t) {
ListNode *h, **c = &h;
while(s && t) {
if(s->val < t->val) {
*c = s;
s = s->next;
} else {
*c = t;
t = t->next;
}
c = &(*c)->next;
}
if(s)
*c = s;
else
*c = t;
return h;
}
w*x
31 楼
啊，不好意思，丢错版本了
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
NODE* mergeTwoList(NODE* p1, NODE* p2)
{
if (NULL == p1 && NULL == p2)
return NULL;
if (NULL == p1) return p2;
if (NULL == p2) return p1;
NODE* pIter1 = p1;
NODE* pIter2 = p2;
NODE* pIter = NULL;
NODE* pHead = NULL;
while (pIter1 != NULL && pIter2 != NULL)
{
NODE* pSmall = NULL;
if (pIter1->nVal < pIter2->nVal)
{
pSmall = pIter1;
pIter1 = pIter1->pNext;
}
else
{
pSmall = pIter2;
pIter2 = pIter2->pNext;
}
if (pIter == NULL)
{
pIter = pSmall;
pHead = pIter;
}
else
{
pIter->pNext = pSmall;
pIter = pIter->pNext;
}
}
if (NULL == pIter1) pIter->pNext = pIter2;
if (NULL == pIter2) pIter->pNext = pIter1;
return pHead;
}
NODE* merge(deque
{
while (links.size() > 1)
{
NODE* p1 = links.front();
links.pop_front();
NODE* p2 = links.front();
links.pop_front();
NODE* p = mergeTwoList(p1, p2);
links.push_back(p);
}
return links.empty() ? NULL : links[0];
}
【在 b*********h 的大作中提到】
: 比如 3 个 lists 吧
: [1, 3, 5]
: [2, 4, 6]
: [3, 3, 3]
: 那个程序第一次 loop 就把 [1, 3, 5] 和 [2, 4, 6] 合起来了？
c*7
32 楼
各位大牛，请看看下面这个算法， 这个是不用heap的算法。
我觉得complexity 是 O(k*n), k是list 的个数， n 是list的平均长度。
那是不是这个应该比用heap的更好点啊？
public static ListNode mergeKLists(ArrayList kLists) {
if (kLists==null)
return null;
if (kLists.size()==0)
return null;
// if there is only one list in kLists
if (kLists.size()==1)
return kLists.get(0);
int length = kLists.size();
// initialize the curList with the first item in the list
ListNode curList = kLists.get(0);
// merge the curList with the rest of the items in the list
// and save the merged list back to curList
for (int i =1; i
}
// return curList as the result
return curList;
}
private static ListNode mergeTwoLists(ListNode l1, ListNode l2){
// if one list is empty, then return the other one
if(l1==null) return l2;
if(l2==null) return l1;
// create two index nodes for the two lists
ListNode indexNode1 = l1;
ListNode indexNode2 = l2;
// create a dummy head node
ListNode dummyHead = new ListNode(-1);
// create an index node for the returning merge list
ListNode indexNode = dummyHead;
// while both lists does not hit its end
while(indexNode1!=null&&indexNode2!=null){
if(indexNode1.val
indexNode.next = indexNode1;
// move to next node in list1
indexNode1 = indexNode1.next;
}else{
// add the node in list2 to the merged list
indexNode.next = indexNode2;
// move to next node in list2
indexNode2 = indexNode2.next;
}
// update the index var in the merged list
indexNode = indexNode.next;
}
// add the rest of nodes in list1 to the returning list
if(indexNode1!=null){
indexNode.next = indexNode1;
}
// add the rest of nodes in list2 to the returning list
if(indexNode2!=null){
indexNode.next = indexNode2;
}
// return the real head
return dummyHead.next;
}
我觉得complexity 是 O(k*n), k是list 的个数， n 是list的平均长度。
那是不是这个应该比用heap的更好点啊？
public static ListNode mergeKLists(ArrayList
if (kLists==null)
return null;
if (kLists.size()==0)
return null;
// if there is only one list in kLists
if (kLists.size()==1)
return kLists.get(0);
int length = kLists.size();
// initialize the curList with the first item in the list
ListNode curList = kLists.get(0);
// merge the curList with the rest of the items in the list
// and save the merged list back to curList
for (int i =1; i
}
// return curList as the result
return curList;
}
private static ListNode mergeTwoLists(ListNode l1, ListNode l2){
// if one list is empty, then return the other one
if(l1==null) return l2;
if(l2==null) return l1;
// create two index nodes for the two lists
ListNode indexNode1 = l1;
ListNode indexNode2 = l2;
// create a dummy head node
ListNode dummyHead = new ListNode(-1);
// create an index node for the returning merge list
ListNode indexNode = dummyHead;
// while both lists does not hit its end
while(indexNode1!=null&&indexNode2!=null){
if(indexNode1.val
indexNode.next = indexNode1;
// move to next node in list1
indexNode1 = indexNode1.next;
}else{
// add the node in list2 to the merged list
indexNode.next = indexNode2;
// move to next node in list2
indexNode2 = indexNode2.next;
}
// update the index var in the merged list
indexNode = indexNode.next;
}
// add the rest of nodes in list1 to the returning list
if(indexNode1!=null){
indexNode.next = indexNode1;
}
// add the rest of nodes in list2 to the returning list
if(indexNode2!=null){
indexNode.next = indexNode2;
}
// return the real head
return dummyHead.next;
}
d*g
33 楼
这个应该不是O(k*n)吧~~在第i个iteration里，需要merge一个长度为n的list 和一个
长度为 i*n的list，最坏情况下复杂度是(i+1)*n。于是总复杂度是 2n+3n+...+kn = O
(n*k^2)。
【在 c****7 的大作中提到】
: 各位大牛，请看看下面这个算法， 这个是不用heap的算法。
: 我觉得complexity 是 O(k*n), k是list 的个数， n 是list的平均长度。
: 那是不是这个应该比用heap的更好点啊？
: public static ListNode mergeKLists(ArrayList
: if (kLists==null)
: return null;
: if (kLists.size()==0)
: return null;
: // if there is only one list in kLists
: if (kLists.size()==1)
p*2
34 楼
我写了一下，放到我博客里了。
http://blog.sina.com.cn/s/blog_b9285de20101hg43.html
http://blog.sina.com.cn/s/blog_b9285de20101hg43.html
l*4
35 楼
mark
【在 c****7 的大作中提到】
: 原题是leetcode上的merge k sorted lists
: http://discuss.leetcode.com/questions/204/merge-k-sorted-lists
: 这个题有好几种解法，比如divide and conquer, priority queue.
: 我写了个priority queue的。我的问题是， 如果现在要做 merge k sorted
: array,怎样来设计这个priority queue才能最简单有效呢？
: 附上 merge-k-sorted-lists的代码
: public static ListNode mergeKLists_priorityQueue(ArrayList kLists)
: {
: // border case
: if(kLists.size()==0) return null;
【在 c****7 的大作中提到】
: 原题是leetcode上的merge k sorted lists
: http://discuss.leetcode.com/questions/204/merge-k-sorted-lists
: 这个题有好几种解法，比如divide and conquer, priority queue.
: 我写了个priority queue的。我的问题是， 如果现在要做 merge k sorted
: array,怎样来设计这个priority queue才能最简单有效呢？
: 附上 merge-k-sorted-lists的代码
: public static ListNode mergeKLists_priorityQueue(ArrayList
: {
: // border case
: if(kLists.size()==0) return null;
相关阅读
有没有人见过一种叫h2b的东西？postdoc还是小公司的research scientist?求指点csG面试题，很难如何在 wechat 自己 profile 里面加照片 ？ (转载)leetcode 150题 划重点有人了解LiveRamp家的Intern面试么？统计phd去药厂，银行还是互联网好？请教一下各位大牛，开放性问题的事情。CS的offer真肥啊 (转载)FB第二轮电面记录关于用STL实现LRU cache2.5年Gap，刚在美拿到offer，LG要海归，自己何时归合适？找到份工作要先有6个月的contract正常吗？这次高通裁员烙印被裁的多还是老中?[Intern] IT BA实习机会Bloomberg的R&D Manager年薪有多少？ (转载)请教OPT 还没有工作期间，有什么医疗保险可以买想转方向，请给建议求推荐波士顿地区的mobile app developer