鏈接在此：Flatten 2D Vector - LeetCode
直接的思路
比較直接的思路就是用兩個pointer踱蛀，p指v里面的子array，q指子array里面妹萨，讀數(shù)就從v[p][q]讀匿辩，然后增加q的值，假如q已經(jīng)到頭了，就再增加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接口主要有三個函數(shù)：
image.png
此處不需要
remove()爷辙，前兩個就夠了。難點在于怎么操作這種2D array的Iterator朦促。Array在Java 8之前是不支持Iterator的（除了一些第三方庫）膝晾，因此至少需要把它轉(zhuǎn)化成List才能用。不過Java 8帶來了stream务冕，可以另辟蹊徑地通過Arrays.stream(arr).iterator()達(dá)到目的血当。有了
Iterator之后，本質(zhì)上還是和雙指針類似，外圍rowIter負(fù)責(zé)遍歷v臊旭，內(nèi)圍colIter負(fù)責(zé)遍歷v[i]落恼。當(dāng)然還是有細(xì)節(jié)不同的，最大的不同是rowIter調(diào)用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撤奸，所以時間復(fù)雜度并未增加。
假如函數(shù)傳入的是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();
}
}
