我在面试中被问到以下问题:
Combine two iterators over their sorted contents such that the resulting iterator should iterate over the combination of these 2 iterators in sorted order in O(1) time (these iterators iterate over a String).
我编写了以下代码,但我确定它不会在 O(1) 时间内执行。对于匹配面试问题设置的约束,您有什么建议?
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class iteratorCombine {
// assumption1: elements are hardcoded
// assumption2: both iterators have equal number of elements
public static void main(String[] args) {
iteratorCombine testObj = new iteratorCombine();
Set<String> firstSet = new TreeSet<String>();
Set<String> secondSet = new TreeSet<String>();
Set<String> combinedSet;
firstSet = testObj.storeElements1(firstSet);
secondSet = testObj.storeElements2(secondSet);
Iterator<String> it1 = firstSet.iterator();
Iterator<String> it2 = secondSet.iterator();
combinedSet = testObj.combine(it1, it2);
// output
Iterator<String> itComb = combinedSet.iterator();
while(itComb.hasNext()){
System.out.println(itComb.next());
}
}
public Set<String> storeElements1(Set<String> firstSet){
firstSet.add("first3");
firstSet.add("first1");
firstSet.add("first2");
return firstSet;
}
public Set<String> storeElements2(Set<String> secondSet){
secondSet.add("second3");
secondSet.add("second1");
secondSet.add("second2");
return secondSet;
}
public Set<String> combine(Iterator<String> it1, Iterator<String>it2){
String firstEle, secondEle;
Set<String> combinedSet = new TreeSet<String>();
while (it1.hasNext() && it2.hasNext()) {
firstEle = it1.next();
secondEle = it2.next();
combinedSet.add(firstEle+secondEle);
}
return combinedSet;
}
}
最佳答案
我相信,如果不扩展 iterator
并支持 peek
功能,您将无法做到这一点。这样的迭代器并不难。这是一种方法。
static class PeekingIterator<T> implements Iterator<T> {
private final Iterator<T> iterator;
private T temp;
public PeekingIterator(Iterator<T> iterator) {
this.iterator = iterator;
}
public T peek() {
//if there is no peek, advance the iterator and store its value, return the peek otherwise
if(temp==null){
temp = this.iterator.next();
}
return temp;
}
@Override
public T next() {
//if we already have a peek,return it and nullify it, otherwise do normal next()
if(temp!=null){
T t = temp;
temp = null;
return t;
}else{
return this.iterator.next();
}
}
@Override
public boolean hasNext() {
return this.iterator.hasNext() || temp!=null;
}
}
一旦可以窥视,剩下的就很简单了,您可以使用两个窥视迭代器构建 SortedIterator
,窥视两个迭代器并推进具有较小元素的迭代器。
static class SortedIterator<T extends Comparable<T>> implements Iterator<T>{
private final PeekingIterator<T> peekingIterator1;
private final PeekingIterator<T> peekingIterator2;
SortedIterator(Iterator<T> source1, Iterator<T> source2){
peekingIterator1 = new PeekingIterator<>(source1);
peekingIterator2 = new PeekingIterator<>(source2);
}
@Override
public boolean hasNext() {
return peekingIterator1.hasNext() || peekingIterator2.hasNext();
}
@Override
public T next() {
if(!peekingIterator1.hasNext()){
return peekingIterator2.next();
}
if(!peekingIterator2.hasNext()){
return peekingIterator1.next();
}
T peek1 = peekingIterator1.peek();
T peek2 = peekingIterator2.peek();
if(peek1.compareTo(peek2)<0){
return peekingIterator1.next();
}
return peekingIterator2.next();
}
}
这里的分析很明显,SortedIterator.next
和SortedIterator.hasNext
在常数时间内运行。
关于java - 在 O(1) 时间内组合两个排序的迭代器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35492948/