y*****e
发帖数: 712 | 1 interface是这个 Iterable mergeKSortedIterators(Iterators[] iters)
也就是给每个array的iterator,然后merge.
我开始想的是用merge k sorted list的办法，用一个heap保存所有的iterator,看哪个
iterator的头个element最小,push to result，然后Move to next element。
需要一个iterator的comparator来sort iterators, 是我的comparator写的不对？还
是heap的operation错了？
不知有人做过这题吗，希望给点建议。。。。
public static class iteratorComp implements Comparator>{
public int compare(Iterator a, Iterator b){
int a1 = 0;
int b1 = 0;
if(a.hasNext()){
a1 = a.next();
}
if(b.hasNext()){
b1 = b.next();
}
return a1 - b1;
}
} |
k******i
发帖数: 11 | 2 iterator直接比的话，比较一次之后next的值就丢失了。 可以创建一个新的数据结构
， 包含iterator和当前的值。
public class IterWrapper{
int currentVal;
Iterator iter;
}
Comparator比较currentVal的大小。初始化的时候对每个iterator取next，然后放进
priorityQueue或者heap。
每次IterWrapper被poll之后，更新currentVal的值再放回去就好了。 |
y*****e
发帖数: 712 | 3 非常感谢，照你写的改了，已经work了！这个小trick很有用！
【在 k******i 的大作中提到】
: iterator直接比的话，比较一次之后next的值就丢失了。 可以创建一个新的数据结构
: ， 包含iterator和当前的值。
: public class IterWrapper{
: int currentVal;
: Iterator iter;
: }
: Comparator比较currentVal的大小。初始化的时候对每个iterator取next，然后放进
: priorityQueue或者heap。
: 每次IterWrapper被poll之后，更新currentVal的值再放回去就好了。
|
l*****n
发帖数: 246 | 4 为啥要把iterator排序？直接存int到heap里面不行吗？
【在 y*****e 的大作中提到】
: interface是这个 Iterable mergeKSortedIterators(Iterators[] iters)
: 也就是给每个array的iterator,然后merge.
: 我开始想的是用merge k sorted list的办法，用一个heap保存所有的iterator,看哪个
: iterator的头个element最小,push to result，然后Move to next element。
: 需要一个iterator的comparator来sort iterators, 是我的comparator写的不对？还
: 是heap的operation错了？
: 不知有人做过这题吗，希望给点建议。。。。
: public static class iteratorComp implements Comparator>{
: public int compare(Iterator a, Iterator b){
: int a1 = 0;
|
y*****e
发帖数: 712 | 5 直接放int就丢失了Iterator了，没法call iter.hasNext().
【在 l*****n 的大作中提到】
: 为啥要把iterator排序？直接存int到heap里面不行吗？
|
k******i
发帖数: 11 | 6 也可以， 自己拿hashmap或者建立一个 int->Iterator的mapping能够提供O(1)lookup
就可以了。然后注意处理一下duplicate value的情况就OK了。
【在 l*****n 的大作中提到】
: 为啥要把iterator排序？直接存int到heap里面不行吗？
|
m******3
发帖数: 346 | 7 没太明白怎么改，楼主能上个code么。
【在 y*****e 的大作中提到】
: 非常感谢，照你写的改了，已经work了！这个小trick很有用！
|
W***o
发帖数: 6519 | 8 re
【在 y*****e 的大作中提到】
: interface是这个 Iterable mergeKSortedIterators(Iterators[] iters)
: 也就是给每个array的iterator,然后merge.
: 我开始想的是用merge k sorted list的办法，用一个heap保存所有的iterator,看哪个
: iterator的头个element最小,push to result，然后Move to next element。
: 需要一个iterator的comparator来sort iterators, 是我的comparator写的不对？还
: 是heap的operation错了？
: 不知有人做过这题吗，希望给点建议。。。。
: public static class iteratorComp implements Comparator>{
: public int compare(Iterator a, Iterator b){
: int a1 = 0;
|
y*****e
发帖数: 712 | 9 public static Iterable mergeKSortedIterators(List
> Iters){
Queue minHeap = new PriorityQueue();
List result = new ArrayList();
for(Iterator iter : Iters){
if(iter.hasNext()){
minHeap.add(new newIter(iter.next(), iter));
}
}
while(!minHeap.isEmpty()){
newIter newiter = minHeap.poll();
result.add(newiter.getValue());
if(newiter.hasNext()){
minHeap.add(newiter);
}
}
return result;
}
private static class newIter implements Comparable{
private Integer value;
private Iterator iter;
public newIter(Integer val, Iterator it){
this.value = val;
this.iter = it;
}
public Integer getValue(){
return this.value;
}
public boolean hasNext(){
if(iter.hasNext()){
value = iter.next();
return true;
}
return false;
}
public int compareTo(newIter a){
return this.value - a.value;
}
}
欢迎大家批评指正！
【在 m******3 的大作中提到】
: 没太明白怎么改，楼主能上个code么。
|
y****9
发帖数: 252 | 10 肉丝，今天我正好做到这个题
我就是逐个合并。也有用min heap的。
https://github.com/YiyangLi/LeetSharp/blob/
4c39851d861e5b46040d7b35f91182721cf94a28/LeetSharp/Q023_MergekSortedLists.cs |
y*****e
发帖数: 712 | 11 C#小哥也做这题？好巧啊。我想问你，multiple way merge和min heap这两种的
complexity是一样的吧，都是nklog(k),假设一共k lists， 每个list有n个elements
cs
【在 y****9 的大作中提到】
: 肉丝，今天我正好做到这个题
: 我就是逐个合并。也有用min heap的。
: https://github.com/YiyangLi/LeetSharp/blob/
: 4c39851d861e5b46040d7b35f91182721cf94a28/LeetSharp/Q023_MergekSortedLists.cs
|
y****9
发帖数: 252 | 12 heap的相对于就是全部元素堆在一起排序了，nk log nk， 如果是逐个合并，对于我写
的那个题目，因为是linked list，所以合并到末尾的时候，你直接接上没合并完的就
可以了。也就是说每一次你是ni or nj，然后是ni+nj or nl，其中i，j，l是
1到 k的整数，即下标。所以总共k-1次，假设平均是m，复杂度是km，由于m和n
同级，你可以理解成是kn。所以逐个合并其实最快。
【在 y*****e 的大作中提到】
: C#小哥也做这题？好巧啊。我想问你，multiple way merge和min heap这两种的
: complexity是一样的吧，都是nklog(k),假设一共k lists， 每个list有n个elements
:
: cs
|
t**r
发帖数: 3428 | |
