LeetCode 281 Zigzag Iterator

LeetCode

Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.

Implement the ZigzagIterator class:

ZigzagIterator(List<int> v1, List<int> v2) initializes the object with the two vectors v1 and v2. boolean hasNext() returns true if the iterator still has elements, and false otherwise.
int next() returns the current element of the iterator and moves the iterator to the next element.

Example 1:

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

Example 2:

Input: v1 = [1], v2 = []
Output: [1]

Example 3:

Input: v1 = [], v2 = [1]
Output: [1]

Constraints: 0 <= v1.length, v2.length <= 1000
1 <= v1.length + v2.length <= 2000 -2<sup>31</sup> <= v1[i], v2[i] <= 2<sup>31</sup> - 1

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

Clarification for the follow-up question:

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”.

Follow-up Example:

Input: v1 = [1,2,3], v2 = [4,5,6,7], v3 = [8,9]
Output: [1,4,8,2,5,9,3,6,7]

题目大意：

求两数组轮替取值的Iterator

解题思路：

将数组和数组下标分别存于新数组中。用一个list_index来记录要取哪个数组

解题步骤：

N/A

注意事项：

1. 用Iterator模板，hasNext也是找到下一个元素为止，由于只有两个数组，所以不用循环。取值是一个二维数组val = self.input[self.list_index][self.index[self.list_index]]
2. next中取值后指针要后移。

Python代码：

class ZigzagIterator(TestCases):

    def __init__(self, v1: List[int], v2: List[int]):
        self.input = [v1, v2]
        self.index = [0, 0]
        self.list_index = 0

    def next(self) -> int:
        if self.hasNext():
            val = self.input[self.list_index][self.index[self.list_index]]
            self.index[self.list_index] += 1
            self.list_index = (self.list_index + 1) % 2
            return val
        return None

    def hasNext(self) -> bool:
        if self.index[self.list_index] < len(self.input[self.list_index]):
            return True
        self.list_index = (self.list_index + 1) % 2
        return self.index[self.list_index] < len(self.input[self.list_index])

算法分析：

时间复杂度为O(n)，空间复杂度O(1)