链接在此：Flatten 2D Vector - LeetCode
直接的思路
比较直接的思路就是用两个pointer，p指v里面的子array，q指子array里面，读数就从v[p][q]读，然后增加q的值，假如q已经到头了，就再增加p并重置p。
值得注意的一点是要处理v里面的空array的情况。可以在hasNext()里面把空array都过滤掉，这样就不会影响。代码：
class Vector2D {
private int p, q;
private final int[][] v;
public Vector2D(int[][] v) {
this.v = v;
p = 0;
q = 0;
}
public int next() {
hasNext();
int val = v[p][q];
q++;
if (q == v[p].length) {
p++;
q = 0;
}
return val;
}
public boolean hasNext() {
while (p < v.length && v[p].length == 0) p++;
return p < v.length;
}
}
此代码击败了99.4%，说明效率还是不错的。
Iterator做法
题目的follow up要求使用Iterator，所以还是尝试一下。
Iterator接口主要有三个函数：
image.png
此处不需要
remove()，前两个就够了。难点在于怎么操作这种2D array的Iterator。Array在Java 8之前是不支持Iterator的（除了一些第三方库），因此至少需要把它转化成List才能用。不过Java 8带来了stream，可以另辟蹊径地通过Arrays.stream(arr).iterator()达到目的。有了
Iterator之后，本质上还是和双指针类似，外围rowIter负责遍历v，内围colIter负责遍历v[i]。当然还是有细节不同的，最大的不同是rowIter调用next()时必须马上赋给colIter，不然就没了。代码如下：
class Vector2D {
private final Iterator<int[]> rowIter;
private Iterator<Integer> colIter;
public Vector2D(int[][] v) {
rowIter = Arrays.stream(v).iterator();
if (rowIter.hasNext()) colIter = Arrays.stream(rowIter.next()).iterator();
}
public int next() {
hasNext();
return colIter.next();
}
public boolean hasNext() {
if (colIter == null) return false;
while (!colIter.hasNext() && rowIter.hasNext()) colIter = Arrays.stream(rowIter.next()).iterator();
return colIter.hasNext();
}
}
stream是Lazy的，意味着Arrays.stream(v).iterator()事先并不会遍历整个v，所以时间复杂度并未增加。
假如函数传入的是List，可能做法更原汁原味一些：
class List2D {
private final Iterator<List<Integer>> rowIter;
private Iterator<Integer> colIter;
public List2D(List<List<Integer>> v) {
rowIter = v.iterator();
if (rowIter.hasNext()) colIter = rowIter.next().iterator();
}
public int next() {
hasNext();
int val = colIter.next();
if (!colIter.hasNext() && rowIter.hasNext()) {
colIter = rowIter.next().iterator();
}
return val;
}
public boolean hasNext() {
if (colIter == null) return false;
while (!colIter.hasNext() && rowIter.hasNext()) colIter = rowIter.next().iterator();
return colIter.hasNext();
}
}
套娃一下，通过Leetcode的测试，证明上面的代码同样是对的：
import java.util.*;
import java.util.stream.Collectors;
public class Vector2D {
private static class List2D {
private final Iterator<List<Integer>> rowIter;
private Iterator<Integer> colIter;
public List2D(List<List<Integer>> v) {
rowIter = v.iterator();
if (rowIter.hasNext()) colIter = rowIter.next().iterator();
}
public int next() {
hasNext();
int val = colIter.next();
if (!colIter.hasNext() && rowIter.hasNext()) {
colIter = rowIter.next().iterator();
}
return val;
}
public boolean hasNext() {
if (colIter == null) return false;
while (!colIter.hasNext() && rowIter.hasNext()) colIter = rowIter.next().iterator();
return colIter.hasNext();
}
}
private final List2D list2D;
public Vector2D(int[][] v) {
List<List<Integer>> lists = Arrays.stream(v)
.map(internalArray -> Arrays.stream(internalArray).boxed().collect(Collectors.toList()))
.collect(Collectors.toList());
list2D = new List2D(lists);
}
public int next() {
return list2D.next();
}
public boolean hasNext() {
return list2D.hasNext();
}
}
