10k

284. Peeking Iterator

Published on

Question

The topic is written a lot, in fact it is very simple, pass in an Iterator to implement an Iterator, support peek operation. peek operation that check the next element but do not move the pointer.

Algorithm

An iterator how to just look at it without taking it out? Java comes with no way. So the only way is to firstnext out and then save. Wait for the next to return the value. So we need to use some data structure to save this value.

I started with the idea of using a list to synchronize the contents of the iterator. It would be much simpler to just operate on the list for subsequent operations.

But in fact, instead of introducing a list to increase the space complexity, we just need a variable to save the value that was fetched during the last peek.

The algorithm is as follows.

  • When peek, if the previous value val has not been peeked, use next to take out the next value and store it in a variable. Return this value; if peeked then val should be a value, directly return. You can't go to next every time you peek to save it, so you'll keep nexting the value.
  • When next, see if val has a value. If it has a value, it means that it has been next when peek operation, return this value directly. And set val to null; if val is null, directly next out.
  • hasNext both to determine that there is nothing left in the iterator and to confirm that val is null.

Val is equivalent to adding a buffer of positions to the original iterator that we can manipulate.

Code 1

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

/*
This methods is my first implementaion which utilize arraylist and cost O(n) space. can be optimized .
*/Can be optimized .

class PeekingIterator implements Iterator<Integer> {
    List<Integer> list;
    int pos;
   public PeekingIterator(Iterator<Integer> iterator) { public PeekingIterator(Iterator<Integer> iterator)
       // initialize any member here.
        this.list = new ArrayList<>();
        while (iterator.hasNext()) {
            list.add(iterator.next());
        }
        this.pos = 0;
   }
   
    // Returns the next element in the iteration without advancing the iterator.
   public Integer peek() {
        if (list.isEmpty()) {
            return -1;
        } else {
            return list.get(pos);
        }
   }
   
   // hasNext() and next() should behave the same as in the Iterator interface.
   // Override them if needed.
   @Override
   public Integer next() {
        return list.get(pos++);
   }
   
   @Override
   public boolean hasNext() {
       return pos < list.size();
   }
}

Code 2

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iter;
    Integer val;
   public PeekingIterator(Iterator<Integer> iterator) { public PeekingIterator(Iterator<Integer> iterator)
       // initialize any member here.
       iter = iterator;
        val = null;
   iter = iterator; val = null; }
   
    // Returns the next element in the iteration without advancing the iterator.
   public Integer peek() {
        if (hasNext()) {
            if (val == null) {
                val = iter.next();
            } 
            return val;
        }
        return null;
   }
   
   // hasNext() and next() should behave the same as in the Iterator interface.
   // Override them if needed.
   @Override
   public Integer next() {
       if (hasNext()) {
            if (val ! = null) {
                int next = val;
                val = null;
                return next;
            }
            return iter.next();
        }
        return null;
   }
   
   @Override
   public boolean hasNext() {
       return val ! = null || iter.hasNext();
   }
}

问题

题目写了很多，其实很简单，传入一个Iterator实现一个Iterator，支持peek操作。peek操作即查next元素但是不移动指针。

算法

一个迭代器如何只查看不取出呢？ Java自带的没办法。所以只能是先next出来，然后保存。等到next的时候去返回这个值。所以需要我们用一些数据结构来保存这个值。

我一开始想的是用list同步迭代器的内容。后续的操作只需要在list上操作就简单多了。

但是其实不用引入一个list增加了空间复杂度，只需要一个变量把上次peek的时候取到的值保存即可。

算法如下：

  • peek的时候，如果之前的这个值val没有peek过，用next取出下一个值并用一个变量存起来。返回这个值；如果被peek过那么val应该是有值的，直接返回。不能每次peek都去next保存，这样会一直next取值。
  • next的时候，看是否val有值，有值说明在peek操作的时候已经被next出来了，直接返回这个值即可。并将val置为空值；如果val为null，直接next出来即可。
  • hasNext既要判断迭代器没有东西了，也要确认val是null。

Val相当于给原来的迭代器加了一个位置的缓冲区可以让我们操作。

代码1

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

/*
This methods is my first implementaion which utilize arraylist and cost O(n) space. Can be optimized .
*/

class PeekingIterator implements Iterator<Integer> {
    List<Integer> list;
    int pos;
   public PeekingIterator(Iterator<Integer> iterator) {
       // initialize any member here.
        this.list = new ArrayList<>();
        while (iterator.hasNext()) {
            list.add(iterator.next());
        }
        this.pos = 0;
   }
   
    // Returns the next element in the iteration without advancing the iterator.
   public Integer peek() {
        if (list.isEmpty()) {
            return -1;
        } else {
            return list.get(pos);
        }
   }
   
   // hasNext() and next() should behave the same as in the Iterator interface.
   // Override them if needed.
   @Override
   public Integer next() {
        return list.get(pos++);
   }
   
   @Override
   public boolean hasNext() {
       return pos < list.size();
   }
}

代码2

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iter;
    Integer val;
   public PeekingIterator(Iterator<Integer> iterator) {
       // initialize any member here.
       iter = iterator;
        val = null;
   }
   
    // Returns the next element in the iteration without advancing the iterator.
   public Integer peek() {
        if (hasNext()) {
            if (val == null) {
                val = iter.next();
            } 
            return val;
        }
        return null;
   }
   
   // hasNext() and next() should behave the same as in the Iterator interface.
   // Override them if needed.
   @Override
   public Integer next() {
       if (hasNext()) {
            if (val != null) {
                int next = val;
                val = null;
                return next;
            }
            return iter.next();
        }
        return null;
   }
   
   @Override
   public boolean hasNext() {
       return val != null || iter.hasNext();
   }
}
Thoughts? Leave a comment