在O(1)时间内组合两个已排序的迭代器

Question

我在接受采访时被问到以下问题:

将两个迭代器组合在它们的排序内容上,这样得到的迭代器应该在O(1)时间内以排序顺序迭代这两个迭代器的组合(这些迭代器迭代一个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;
  }
}

Answer 1

如果你不扩展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在恒定的时间内运行.