C++ with queue (compatible with k vectors)


  • 74
    L
    class ZigzagIterator {
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) {
            if (v1.size() != 0)
                Q.push(make_pair(v1.begin(), v1.end()));
            if (v2.size() != 0)
                Q.push(make_pair(v2.begin(), v2.end()));
        }
    
        int next() {
            vector<int>::iterator it = Q.front().first;
            vector<int>::iterator endIt = Q.front().second;
            Q.pop();
            if (it + 1 != endIt)
                Q.push(make_pair(it+1, endIt));
            return *it;
        }
    
        bool hasNext() {
            return !Q.empty();
        }
    private:
        queue<pair<vector<int>::iterator, vector<int>::iterator>> Q;
    };
    

    somehow similar to BFS.


  • 0
    This post is deleted!

  • 0
    K

    Nice! It is indeed compatible!


  • 8
    K

    Similar idea in Java.

    public class ZigzagIterator {
        LinkedList<Iterator> list;
        public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
            list = new LinkedList<Iterator>();
            if(!v1.isEmpty()) list.add(v1.iterator());
            if(!v2.isEmpty()) list.add(v2.iterator());
        }
    
        public int next() {
            Iterator poll = list.remove();
            int result = (Integer)poll.next();
            if(poll.hasNext()) list.add(poll);
            return result;
        }
    
        public boolean hasNext() {
            return !list.isEmpty();
        }
    }

  • 1
    C

    Python Version

    class ZigzagIterator(object):
    
        def __init__(self, v1, v2):
            """
            Initialize your data structure here.
            :type v1: List[int]
            :type v2: List[int]
            """
            self.q = []
            if len(v1) != 0:
                self.q.append(v1)
            if len(v2) != 0:
                self.q.append(v2)
                    
        def next(self):
            if self.hasNext():
                v = self.q.pop(0)
                val = v.pop(0)
                if len(v) != 0:
                    self.q.append(v)
                return val
        
        def hasNext(self):
            return len(self.q) != 0:

  • 0
    G

    good solution! very clean code!


  • 0

    Thanks for your solution! This is very helpful.


  • 0

    I also have a very similar solution without using iterator, seems it works too.

    class ZigzagIterator {
    private:
        vector<vector<int>> _nums; // member array;
        queue<pair<int, int>> Que; // processing queue;
    
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) {
            if(v1.size()) _nums.push_back(v1);
            if(v2.size()) _nums.push_back(v2);
            for(int i = 0; i < _nums.size(); i++) {
                Que.push(make_pair(i, 0));
            }
        }
    
        int next() {
            auto nxt = Que.front();
            Que.pop();
            int i = nxt.first;
            int j = nxt.second;
            if(j < _nums[i].size() - 1) Que.push({i, j + 1});
            return _nums[i][j];
        }
    
        bool hasNext() {
            return Que.size() > 0;
        }
    };

  • 0
    P

    Pretty clean solution... loved it.


  • 0
    G

    great solution! Love it!


  • 0
    A

    @chenhaoyu What is the space complexity?
    Is it O(v1+v2) since we are storing the two lists in the queue?


  • 0
    A

    @kevinhsu What is the space complexity?


  • 0
    H

    The queue method works well with k vectors, I tried to make it fewer lines

    ...
    class ZigzagIterator {
    public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
    q.push(make_pair(v1.begin(), v1.end()));
    q.push(make_pair(v2.begin(), v2.end()));
    }

    int next() {
        int res = *q.front().first++;
        q.push(q.front());
        q.pop();
        return res;
    }
    
    bool hasNext() {
        while(!q.empty() && q.front().first == q.front().second) q.pop();
        return !q.empty();
    }
    

    private:
    queue<pair<vector<int>::iterator, vector<int>::iterator>> q;

    };


  • 0
    H

    @Ximin.Z Yeah, it works. But using iterator only requires constant space while your method requires O(n) space


Log in to reply
 

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