Python O(1) space solution for k-vector


  • 0
    V
    class ZigzagIterator(object):
        def __init__(self, v1, v2):
            """
            Initialize your data structure here.
            :type v1: List[int]
            :type v2: List[int]
            """
            self.v = [v1, v2]
            self.n = 0
    
        def next(self):
            """
            :rtype: int
            """
            start = self.n
            # find the next not-null vector 
            while len(self.v[self.n]) == 0:
                self.n = (self.n+1) % len(self.v)
                if self.n == start:     # one loop
                    return
                
            res = self.v[self.n].pop(0)
            self.n = (self.n+1) % len(self.v)
            
            return res
                
    
        def hasNext(self):
            """
            :rtype: bool
            """
            # start from self.n
            for i in range(self.n, self.n + len(self.v)):
                i %= len(self.v)
                if len(self.v[i]) > 0:
                    return True
            return False
    
    # Your ZigzagIterator object will be instantiated and called as such:
    # i, v = ZigzagIterator(v1, v2), []
    # while i.hasNext(): v.append(i.next())

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.