LeetCode 281 Zigzag Iterator

LeetCode

<div>

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:

<pre>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]. </pre>

Example 2:

<pre>Input: v1 = [1], v2 = [] Output: [1] </pre>

Example 3:

<pre>Input: v1 = [], v2 = [1] Output: [1] </pre>

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:

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

</div>

题目大意：

求两数组轮替取值的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)