7-9 lines added, Java and C++, O(1) space.


  • 86

    Since the OJ does while (i.hasNext()) cout << i.next();, i.e., always calls hasNext before next, I don't really have to call it myself so I could save that line in next. But I think that would be bad, we shouldn't rely on that.

    C++

    class Vector2D {
        vector<vector<int>>::iterator i, iEnd;
        int j = 0;
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            i = vec2d.begin();
            iEnd = vec2d.end();
        }
    
        int next() {
            hasNext();
            return (*i)[j++];
        }
    
        bool hasNext() {
            while (i != iEnd && j == (*i).size())
                i++, j = 0;
            return i != iEnd;
        }
    };
    

    Java

    public class Vector2D {
    
        private Iterator<List<Integer>> i;
        private Iterator<Integer> j;
    
        public Vector2D(List<List<Integer>> vec2d) {
            i = vec2d.iterator();
        }
    
        public int next() {
            hasNext();
            return j.next();
        }
    
        public boolean hasNext() {
            while ((j == null || !j.hasNext()) && i.hasNext())
                j = i.next().iterator();
            return j != null && j.hasNext();
        }
    }

  • 0

    Great idea using the fact that elements in vector are stored in a contiguous range of memory? Moreover, hasNext() handles empty vectors elegantly.


  • 0

    "Great idea using the fact that elements in vector are stored in a contiguous range of memory?"

    I'm not sure that counts as an idea. At least I certainly didn't think about it. Or maybe I don't know what you mean :-)

    And yeah, I'm pretty happy with my hasNext.


  • 0

    The Java version seems interesting :-)


  • 0
    This post is deleted!

  • 0
    C

    Very elegant solution!


  • 0

    Wow! Awesome!


  • 0
    L

    why need to call hasNext() inside next() method?


  • 0

    @covebysea Because someone could call next without having called hasNext beforehand.


  • 0
    S

    Hi Stefan, how would you write a Python version? Thanks!


  • 0

    There are so many ways... here's one (not a particularly good one, but I like these :-)

    class Vector2D:
        def __init__(self, vec2d):
            vec = sum(vec2d, [])[::-1]
            self.hasNext = lambda: bool(vec)
            self.next = vec.pop

  • 1

    Ok here's a more standard and more efficient way:

    class Vector2D:
    
        def __init__(self, vec2d):
            self.data = itertools.chain.from_iterable(vec2d)
            self.n = sum(map(len, vec2d))
    
        def next(self):
            self.n -= 1
            return next(self.data)
    
        def hasNext(self):
            return self.n > 0
    

  • 0
    Y

    another great code by @StefanPochmann


  • 0
    D

    then why not have if(hasNext()) return j.next() inside the next() method? Simply call the method will do any work?


  • 0

    @Dengke Huh? You want to add unnecessary code? Why? You'd probably also have to add an unconditional return, or else Java will complain. And yes, calling a method executes it so it does what it does.


  • 0
    N

    @StefanPochmann, what's purpose of hasNext(); in the next function? No matter it returns true of false, the (*i)[j++] value is always returned, isn't it?


  • 4
    X

    @needforspeed Because if you don't call hasNext(), j can not be changed to the next row when the current row is ended.


  • 0
    X

    Beautiful architecture with that hasNext() !


  • 0
    D

    Can some explain this code in a very simple way?


  • 0
    Y

    can we return i.hasNext() in hasNext()?


Log in to reply
 

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