251. Flatten 2D Vector

发表于 | 分类于

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
[1,2],
[3],
[4,5,6]
]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

解法1： Non-Iterator, List + Pointer

用一个list来存储原来的数据。同时维护两个指针，一个指向当前的子list，另一个指向该list中的位置。在hasNext函数中，判断是否还有数据查看elemenPointer是不是在list尾巴，同时检查是否还有下一个list。

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Vector2D implements Iterator<Integer> {
    List<List<Integer>> data;
    int listPos;
    int elemPos;
    public Vector2D(List<List<Integer>> vec2d) {
        this.data = vec2d;
        listPos = 0;
        elemPos = 0;
    }
    @Override
    public Integer next() {
        return data.get(listPos).get(elemPos++);
    }
    @Override
    public boolean hasNext() {
        while (listPos < data.size()) {
            if (elemPos < data.get(listPos).size()) {
                return true;
            } else {
                listPos++;
                elemPos = 0;
            }
        }
        return false;
    }
}
/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */

解法2： Iterator

用一个queue来存储每一个list对应的iterator。同时维护一个iterator指向当前的iterator。hasNext就需要判断当前是否还有iterator同时这个iterator是否有下一个元素。

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Vector2D implements Iterator<Integer> {
    Queue<Iterator<Integer>> queue;
    Iterator<Integer> current = null;
    public Vector2D(List<List<Integer>> vec2d) {
        queue = new LinkedList<>();
        for (List<Integer> list : vec2d) {
            queue.offer(list.iterator());
        }
        current = queue.poll();
    }
    @Override
    public Integer next() {
        return current.next();
    }
    @Override
    public boolean hasNext() {
        while (current == null || !current.hasNext()) {
            if (!queue.isEmpty()) {
                current = queue.poll();
            } else {
                return false;
            }
        }
        return true;
    }
}
/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */