251.Flatten_2D_Vector.md

251. Flatten 2D Vector

中等 https://leetcode-cn.com/problems/flatten-2d-vector/submissions/

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.

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

相关企业

• 爱彼迎 Airbnb|8

相关标签

• Design
• Array
• Two Pointers
• Iterator

相似题目

• Binary Search Tree Iterator 中等
• Zigzag Iterator 中等
• Peeking Iterator 中等
• Flatten Nested List Iterator 中等

隐藏提示1

• How many variables do you need to keep track?

隐藏提示2

• Two variables is all you need. Try with x and y.

隐藏提示3

• Beware of empty rows. It could be the first few rows.

隐藏提示4

• To write correct code, think about the invariant to maintain. What is it?

隐藏提示5

• The invariant is x and y must always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it?

隐藏提示6

• Not sure? Think about how you would implement hasNext(). Which is more complex?

隐藏提示7

• Common logic in two different places should be refactored into a common method.

solution v1 - for loop - O(n^2)

can be O(n) if input is List<List> vec insted of int[][]

class Vector2D {

    private List<Integer> allElements; 
    private Integer currIndex;

    public Vector2D(int[][] vec) {
        if (vec == null || vec.length ==0){
            return;
        }

        this.allElements = new ArrayList<Integer>();
        for (int i = 0; i < vec.length; i ++){
            if (vec[i] != null && vec[i].length != 0){
                for (int j = 0; j < vec[i].length; j ++){
                    this.allElements.add(vec[i][j]);
                }
                // Collections.addAll(this.allElements, vec[i]); //This leads to error bc int is not Integer
            }
        }
        this.currIndex = -1;
    }
    
    public int next() {
        if (this.allElements != null && this.currIndex <= this.allElements.size() - 2){
            this.currIndex += 1;
            return this.allElements.get(this.currIndex);
        }
        return -1;
    }
    
    public boolean hasNext() {
        if (this.allElements != null && this.currIndex <= allElements.size() - 2){
            return true;
        }
        return false;
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D obj = new Vector2D(vec);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

O(n) bc using extend() in py

class Vector2D:

    def __init__(self, vec: List[List[int]]):
        self.allElements = list()
        self.currIndex = -1
        if not vec:
            return

        for vec_i in vec:
            if vec_i: # if not not vec_i:
                self.allElements.extend(vec_i)

    def next(self) -> int:
        if self.currIndex <= len(self.allElements) - 2:
            self.currIndex += 1
            return self.allElements[self.currIndex]
        return -1

    def hasNext(self) -> bool:
        if self.currIndex <= len(self.allElements) - 2:
            return True
        return False



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