如何通过一个整数列表的迭代器返回偶数的迭代器？

Question

我在一次Java面试中被问及这个问题。我有一个整数列表的迭代器。我需要编写一个函数，它接受此迭代器作为参数，并返回仅包含偶数的迭代器。我被告知，我不能修改原始的数字列表。因此，从列表中删除奇数不是解决方案。请给予建议。谢谢。

- lini sax

Answer 1

你基本上只需要创建一个新的迭代器，该迭代器接受现有的迭代器并覆盖其hasNext和next方法。唯一的困难在于，一个表现良好的迭代器显然只需要O(1)空间，因此创建一个新列表并使用它是不好的风格 - 因此我们需要一些记录。类似以下内容的简化伪代码（假设null为无效值等） - 为了某种通用解决方案，应该能够给你基本的思路：

Iterator<T> it;
T next;

NewIterator(Iterator<T> it) {
    this.it = it;
    setNext();
}

void setNext() {
    while (it.hasNext()) {
        T val = it.next();
        if (validT(val)) {
            next = val;
            return;
        }
    }
    next = null; // lets assume null is invalid.
}

boolean hasNext() {
    return next != null;
}

T next() {
   T ret = next;
   setNext();
   return ret;
}

- Voo

---

我认为这基本上是正确的。setNext在时间上是无限制的。因此，setNext，hasNext和next应该同步。 - emory

我不确定构造函数已经开始扫描底层迭代器是否可接受... - Kaarel

@Kaarel 好的，你可以轻松更改它，但是你唯一能够这样做的其他可能地方就是在 hasNext 调用中，而我认为那样做更糟糕。 - Voo

Answer 2

Iterator<Integer> itr;
int cur;

OddIterator(Iterator<Integer> itr) {
    this.itr = itr;
    cur = 0;
}

public boolean hasNext() {
    if ((cur & 1) == 1) {
        return true;
    }
    while (itr != null && itr.hasNext()) {
        cur = itr.next();
        if ((cur & 1) == 1) {
            return true;
        }
    }
    return false;
}

public int next() {
    if (!hasNext()) {
        throw new NoSuchElementException();
    }
    int tmp = cur;
    cur = 0;
    return tmp;
}

希望这对你有所帮助。如果我的代码有任何错误，请告诉我。

- Rui Tong