251. Flatten 2D Vector

双指针+vector

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 105 calls will be made to next and hasNext.

分析

lazy evaluation.

advance函数负责外指针移动,next 负责内指针,hasnext判断外指针

```python3
class Vector2D:

    def __init__(self, vec: List[List[int]]):
        self.vector = vec
        self.outer = 0
        self.inner = 0

    def __advance__(self):
        while self.outer < len(self.vector) and self.inner == len(self.vector[self.outer]):
            self.outer += 1
            self.inner = 0

    def next(self) -> int:
        self.__advance__()
        res = self.vector[self.outer][self.inner]
        self.inner += 1
        return res

    def hasNext(self) -> bool:
        self.__advance__()
        return self.outer < len(self.vector)

# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(vec)
# param_1 = obj.next()
# param_2 = obj.hasNext()
```

Last updated

Was this helpful?