LeetCode 251 Flatten 2D Vector

LeetCode

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 vector vec. next() returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls to next are valid.
hasNext() returns true if there are still some elements in the vector, and false otherwise.

Example 1:

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

Constraints: 0 <= vec.length <= 200
0 <= vec[i].length <= 500 -500 <= vec[i][j] <= 500
At most 10<sup>5</sup> calls will be made to next and hasNext.

*Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.

题目大意：

实现二维Vector的Iterator

解题思路：

用两个指针

解题步骤：

N/A

注意事项：

1. 单一Vector可以是空，所以next要循环找到非空的vector
2. next要col_id加一

Python代码：

class 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都不会空