[Locked] Zigzag Iterator

Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18):
The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input:

[1,2,3]
[4,5,6,7]
[8,9]

It should return [1,4,8,2,5,9,3,6,7].

分析：

　　当k不大于2时，这题解法很直观，交替读两个vector，当其中一个读到尾部的时候，设一个读完的标记，直到两个vector都读完；当k大于2时，也可以使用上述方法，不过复杂度将会是O(k*Nmax)，其中Nmax为最长一个vector的元素个数，也就是说，当其中一个vector为N，N很大，其他vector都不包含元素时，即为稀疏矩阵时，复杂度也会是O(k*N)，即遍历了整个稀疏矩阵，虽然按道理复杂度应该为O(N)才合适，为了解决这个问题，只需要将未读完的数组用一个标记放在某个数据结构里交替来读即可。

　　这题我取巧用一个vector先遍历了一遍原稀疏矩阵，事实上并不需要这么做，只需要在类中保存当前i, j以及存储的未访问完vector编号的set即可。

代码：

class Solution {
private:
    vector<int> result;
    int index;
public:
    Solution(vector<vector<int> > v) {
        index = 0;
        set<int> myset;
        for(int i = 0; i < v.size(); i++)
            if(!v[i].empty())
                myset.insert(i);
        int col = 0;
        while(!myset.empty()) {
            auto row = myset.begin();
            while(row != myset.end()) {
                result.push_back(v[*row][col]);
                if(v[*row].size() - 1 == col)
                    myset.erase(row++);
                else
                    row++;
            }
            col++;
        }
    }
    int next() {
        return result[index++];
    }
    bool hasNext() {
        return index < result.size();
    }
};

[Locked] Zigzag Iterator

原文：http://www.cnblogs.com/littletail/p/5203253.html