# 601.Flatten 2D Vector

## 1.Description(Medium)

Implement an iterator to flatten a 2d vector.

**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]`.

[**Tags**](https://www.lintcode.com/en/problem/flatten-2d-vector/#tags)

[Airbnb](https://www.lintcode.com/tag/airbnb/) [Zenefits](https://www.lintcode.com/tag/zenefits/) [Google](https://www.lintcode.com/tag/google/) [Twitter](https://www.lintcode.com/tag/twitter/)

## 2.Code

```
public class Vector2D implements Iterator<Integer> {

    public Vector2D(List<List<Integer>> vec2d) {
        // Initialize your data structure here
    }

    @Override
    public Integer next() {
        // Write your code here
    }

    @Override
    public boolean hasNext() {
        // Write your code here
    }

    @Override
    public void remove() {}
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */
```

Hint:

1. How many variables do you need to keep track?
2. Two variables is all you need. Try with `x` and `y`
3. Beware of empty rows. It could be the first few rows.
4. To write correct code, think about the [invariant](https://en.wikipedia.org/wiki/Invariant_\(computer_science\)) to maintain. What is it?
5. The invariant is `x`and `y`must always point to a valid point in the 2d vector. Should you maintain your invariant&#x20;

   *ahead of time \_or  \_right when you need it*?
6. Not sure? Think about how you would implement `hasNext()`. Which is more complex?
7. Common logic in two different places should be refactored into a common method.

**Version 1: 数组法：时间 O(N) 空间 O(1)**

这道题让我们压平一个二维向量数组，并且实现一个iterator的功能，包括next和hasNext函数，那么最简单的方法就是

将二维数组按顺序先存入到一个一维数组里（类变量），

然后此时只要维护一个变量i来记录当前遍历到的位置类变量（），

hasNext函数看当前坐标是否小于元素总数，

next函数即为取出当前位置元素，坐标后移一位.

```
public class Solution_601 implements Iterator<Integer>{

    private int[] counter;
    private int cnt=0;//用来计数next和判断是否hasNext，用一个全局变量来保持一致

    public Solution_601(List<List<Integer>> vec2d) {
        // Initialize your data structure here
        int sum=0;
        if(vec2d==null){
            counter=new int[0];
        }else{
            //计算数组的大小,并定义counter数组的大小
            for(List<Integer> list : vec2d){
                if(list!=null){
                    sum=sum+list.size();
                }
            }

            counter=new int[sum];

            //把每个元素放进数组
            int index=0;
            for(List<Integer> list: vec2d){
                for(int i: list){
                    counter[index++]=i;
                }
            }
        }
    }

    @Override
    public Integer next() {
        int value=0;
        if(cnt<counter.length){
            value=counter[cnt];                         
        }
        cnt++;//用一个全局变量来保持一致
        return value;
    }

    @Override
    public boolean hasNext() {
        return cnt<counter.length;
    }

    @Override
    public void remove() {}

}
```

**Version 2: 双指针**

下面我们来看另一种解法，不直接转换为一维数组，而是维护两个变量x和y，我们将x和y初始化为0，对于hasNext函数，我们检查当前x是否小于总行数，y是否和当前行的列数相同，如果相同，说明要转到下一行，则x自增1，y初始化为0，若此时x还是小于总行数，说明下一个值可以被取出来，那么在next函数就可以直接取出行为x，列为y的数字，并将y自增1

```
public class Vector2D {

    private List<List<Integer>> vec2d;
    private int rowId;
    private int colId;
    private int numRows;

    public Vector2D(List<List<Integer>> vec2d) {
        this.vec2d = vec2d;
        rowId = 0;
        colId = 0;
        numRows = vec2d.size();
    }

    public int next() {
        int ans = 0;

        if (colId < vec2d.get(rowId).size()) {
            ans = vec2d.get(rowId).get(colId);
        }

        colId++;

        if (colId == vec2d.get(rowId).size()) {
            colId = 0;
            rowId++;
        }

        return ans;
    }

    public boolean hasNext() {
        while (rowId < numRows && (vec2d.get(rowId) == null || vec2d.get(rowId).isEmpty())) {
            rowId++;
        }

        return vec2d != null && 
        !vec2d.isEmpty() &&
        rowId < numRows;
    }
}
```

**Version 3：双迭代法 ：**&#x65F6;间 O(N) 空间 O(1)

维护两个迭代器：一个是输入的List\<List\<Integer>>的迭代器，它负责遍历List\<Integer>的迭代器。另一个则是List\<Integer>的迭代器，它负责记录当前到哪一个List的迭代器了。每次next时，我们先调用一下hasNext，确保当前List的迭代器有下一个值。

```
public class Vector2D {

    Iterator<List<Integer>> it;
    Iterator<Integer> curr;

    public Vector2D(List<List<Integer>> vec2d) {
        it = vec2d.iterator();
    }

    public int next() {
        hasNext();
        return curr.next();
    }

    public boolean hasNext() {
        // 当前列表的迭代器为空，或者当前迭代器中没有下一个值时，需要更新为下一个迭代器
        while((curr == null || !curr.hasNext()) && it.hasNext()){
            curr = it.next().iterator();
        }
        return curr != null && curr.hasNext();
    }
}
```