<div>
Design an iterator to flatten a 2D vector. It should support the next and hasNext operations.
Implement the Vector2D class:
Vector2D(int[][] vec)initializes the object with the 2D vectorvec.next()returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls tonextare valid.hasNext()returnstrueif there are still some elements in the vector, andfalseotherwise.
Example 1:
<pre>Input ["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"] [[[[1, 2], [3], [4]]], [], [], [], [], [], [], []] Output [null, 1, 2, 3, true, true, 4, false]
Explanation Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]); vector2D.next(); // return 1 vector2D.next(); // return 2 vector2D.next(); // return 3 vector2D.hasNext(); // return True vector2D.hasNext(); // return True vector2D.next(); // return 4 vector2D.hasNext(); // return False </pre>
Constraints:
0 <= vec.length <= 2000 <= vec[i].length <= 500-500 <= vec[i][j] <= 500- At most
10<sup>5</sup>calls will be made tonextandhasNext.
Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.
</div>
题目大意：
实现二维Vector的Iterator
解题思路：
用两个指针
解题步骤：
N/A
注意事项：
- 单一Vector可以是空，所以next要循环找到非空的vector
- next要col_id加一
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Vector2D(TestCases):
def __init__(self, vec: List[List[int]]):
self.vec = vec
self.row_id = 0
self.col_id = 0
def next(self) -> int:
if self.hasNext():
val = self.vec[self.row_id][self.col_id]
self.col_id += 1 # remember
return val
return None
def hasNext(self) -> bool:
while self.row_id < len(self.vec) and self.col_id == len(self.vec[self.row_id]): # remember while coz []
self.row_id += 1
self.col_id = 0
if self.row_id == len(self.vec):
return False
else:
return True
算法分析：
每个操作时间复杂度为O(V/N)或O(1)，空间复杂度O(1), N为所有数，V为vector数，O(N + V)/N. O(1)如果vector都不会空
