java - 快速获取两个有序迭代的公共(public)项的方法？

Question

如何获取两个有序可迭代对象的共同项？ apache commons 或 Guava 或任何此类库是否有任何使用快速算法来实现的库方法？

Answer 1

假设您的元素具有可比性:

List<E> res = new ArrayList<>();
Iterator<E> it1 = orderedIterables1.iterator();
Iterator<E> it2 = orderedIterables2.iterator();
if(!it1.hasNext() || !it2.hasNext()) { // is one of the iterables empty?
    return res;
}
E e1 = it1.next();
E e2 = it2.next();
while(it1.hasNext() && it2.hasNext()) {  // go through each iterable
    int c = e1.compareTo(e2);
    if(c == 0) {
        res.add(e1);
        e1 = it1.next();
        e2 = it2.next();
    } else if(c < 0) {   // e1 is lesser than e2, so take next e1
        e1 = it1.next();
    } else {             // e2 is lesser than e1, so take next e2
        e2 = it2.next();
    }
}
// one of the iterables has now been exhausted 
int c = e1.compareTo(e2);
if(c < 0) {
    while(c < 0 && it1.hasNext()) {  // while e1 < e2, let's take the next e1!
        e1 = it1.next();
        c = e1.compareTo(e2);
    }
} else if(c > 0) {
    while(c > 0 && it2.hasNext()) {  // while e2 < e1, let's take the next e2!
        e2 = it2.next();
        c = e1.compareTo(e2);
    }
}
if(c == 0) {
    res.add(e1);
}