b*****u
发帖数: 648 | 1 今天动手做了一下才发现挺复杂
用heap做怎么由value反查到相应的list？用哈希表的话是否需要 >
因为可能有重复value? 这样代码写起来好麻烦啊。
另外两两merge的方法，和heap的时间开销一样对吧，都是（nlogk) 假设k个list，总
共n个数 |
c********t
发帖数: 5706 | 2 要自己写一个 pair{ int index; int value} structure or class
>
【在 b*****u 的大作中提到】
: 今天动手做了一下才发现挺复杂
: 用heap做怎么由value反查到相应的list？用哈希表的话是否需要 >
: 因为可能有重复value? 这样代码写起来好麻烦啊。
: 另外两两merge的方法，和heap的时间开销一样对吧，都是（nlogk) 假设k个list，总
: 共n个数
|
B********t
发帖数: 147 | 3 为啥要保存value? 保存linked list node pointer不好了？
>
【在 b*****u 的大作中提到】
: 今天动手做了一下才发现挺复杂
: 用heap做怎么由value反查到相应的list？用哈希表的话是否需要 >
: 因为可能有重复value? 这样代码写起来好麻烦啊。
: 另外两两merge的方法，和heap的时间开销一样对吧，都是（nlogk) 假设k个list，总
: 共n个数
|
p*****p
发帖数: 379 | 4 heap直接放node就行了啊，贴个java的，c++也一样的
public class Solution {
public ListNode mergeKLists(ArrayList lists) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode root = null;
ListNode current = null;
if (lists.isEmpty()) return null;
Queue queue = new PriorityQueue(lists.size(), new
Comparator() {
public int compare(ListNode n1, ListNode n2) {
return n1.val - n2.val;
}
});
for (ListNode node : lists) {
if (node == null) continue;
queue.offer(node);
}
while (queue.size() > 0) {
ListNode node = queue.poll();
if (node.next != null) {
queue.offer(node.next);
}
if (root == null) {
root = node;
current = node;
}
else {
current.next = node;
current = current.next;
}
}
return root;
}
}
>
【在 b*****u 的大作中提到】
: 今天动手做了一下才发现挺复杂
: 用heap做怎么由value反查到相应的list？用哈希表的话是否需要 >
: 因为可能有重复value? 这样代码写起来好麻烦啊。
: 另外两两merge的方法，和heap的时间开销一样对吧，都是（nlogk) 假设k个list，总
: 共n个数
|
c********t
发帖数: 5706 | 5 原题是merge k way linkedlist啊, 做了一遍leetcode, 都忘了，
【在 p*****p 的大作中提到】
: heap直接放node就行了啊，贴个java的，c++也一样的
: public class Solution {
: public ListNode mergeKLists(ArrayList lists) {
: // Start typing your Java solution below
: // DO NOT write main() function
: ListNode root = null;
: ListNode current = null;
: if (lists.isEmpty()) return null;
: Queue queue = new PriorityQueue(lists.size(), new
: Comparator() {
|
b*****u
发帖数: 648 | 6 多谢!
还是平时对priority_queue玩得不够熟，都没试过重载Compare()
【在 p*****p 的大作中提到】
: heap直接放node就行了啊，贴个java的，c++也一样的
: public class Solution {
: public ListNode mergeKLists(ArrayList lists) {
: // Start typing your Java solution below
: // DO NOT write main() function
: ListNode root = null;
: ListNode current = null;
: if (lists.isEmpty()) return null;
: Queue queue = new PriorityQueue(lists.size(), new
: Comparator() {
|
l********5
发帖数: 230 | 7 最后的if else是干什么的呀？？
【在 p*****p 的大作中提到】
: heap直接放node就行了啊，贴个java的，c++也一样的
: public class Solution {
: public ListNode mergeKLists(ArrayList lists) {
: // Start typing your Java solution below
: // DO NOT write main() function
: ListNode root = null;
: ListNode current = null;
: if (lists.isEmpty()) return null;
: Queue queue = new PriorityQueue(lists.size(), new
: Comparator() {
|
