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

Airbnb Zenefits Google 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 to maintain. What is it?

5. The invariant is xand ymust always point to a valid point in the 2d vector. Should you maintain your invariant

   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：双迭代法 ：时间 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();
    }
}