由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - L家的高频题merge k sorted arrays giving iterators求讨论!
相关主题
reverse an array问个算法题
hash_map 的遍历问题请教一道数据结构的设计题
Scala怎么通过index访问set或者array我发现我竟然学会了12种tree traversal的办法
请教个面经里的设计题请问怎样写没有parent pointer的BST iterator?
刷了半天题讨论一个题目
一道算法题目一个实际碰到的问题
array contains two integer that sum up to 7combinations 有没有 iterative的方法阿 ?
问个题目,找不在区间内的所有数发T家onsite面筋,dropbox题目,求问几道l家经典题
相关话题的讨论汇总
话题: integer话题: iterator话题: newiter话题: iterators话题: public
1 (共1页)
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
13
mark了,最近讨论气氛很浓啊
1 (共1页)
相关主题
发T家onsite面筋,dropbox题目,求问几道l家经典题刷了半天题
An interview question of finding the median in a moving window.一道算法题目
Google onsite归来array contains two integer that sum up to 7
问一道题(9)问个题目,找不在区间内的所有数
reverse an array问个算法题
hash_map 的遍历问题请教一道数据结构的设计题
Scala怎么通过index访问set或者array我发现我竟然学会了12种tree traversal的办法
请教个面经里的设计题请问怎样写没有parent pointer的BST iterator?
相关话题的讨论汇总
话题: integer话题: iterator话题: newiter话题: iterators话题: public