鏈接在此：Flatten 2D Vector - LeetCode
直接的思路
比較直接的思路就是用兩個(gè)pointer，p指v里面的子array，q指子array里面，讀數(shù)就從v[p][q]讀，然后增加q的值，假如q已經(jīng)到頭了，就再增加p并重置p。
值得注意的一點(diǎn)是要處理v里面的空array的情況。可以在hasNext()里面把空array都過(guò)濾掉，這樣就不會(huì)影響。代碼：
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%，說(shuō)明效率還是不錯(cuò)的。
Iterator做法
題目的follow up要求使用Iterator，所以還是嘗試一下。
Iterator接口主要有三個(gè)函數(shù)：
image.png
此處不需要
remove()，前兩個(gè)就夠了。難點(diǎn)在于怎么操作這種2D array的Iterator。Array在Java 8之前是不支持Iterator的（除了一些第三方庫(kù)），因此至少需要把它轉(zhuǎn)化成List才能用。不過(guò)Java 8帶來(lái)了stream，可以另辟蹊徑地通過(guò)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()時(shí)必須馬上賦給colIter，不然就沒(méi)了。代碼如下：
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()事先并不會(huì)遍歷整個(gè)v，所以時(shí)間復(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();
}
}
套娃一下，通過(guò)Leetcode的測(cè)試，證明上面的代碼同樣是對(duì)的：
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();
}
}
