难度: Medium
Submission
运行时间: 33 ms
内存: 16.3 MB
from collections import deque
class ZigzagIterator:
def __init__(self, v1: List[int], v2: List[int]):
self.queue = deque()
for arr in [v1, v2]:
if arr: self.queue.append((arr, 0))
def next(self) -> int:
val = None
arr, idx = self.queue.popleft()
val = arr[idx]
idx += 1
if idx < len(arr):
self.queue.append((arr, idx))
return val
def hasNext(self) -> bool:
for arr, idx in self.queue:
if idx < len(arr):
return True
return False
# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())
Explain
这个题解使用队列（deque）来实现锯齿迭代器。初始化时，将非空的输入数组及其初始下标 0 作为元组依次加入队列。每次调用 next() 方法时，从队首取出当前要迭代的数组和下标，返回当前元素，并将下标加 1。如果更新后的下标没有超出数组范围，则将新的元组加入队尾。hasNext() 方法则遍历队列中的所有元组，判断是否存在还未迭代完的数组。
时间复杂度: O(m+n+k)
空间复杂度: O(1)
from collections import deque
class ZigzagIterator:
def __init__(self, v1: List[int], v2: List[int]):
# 初始化队列
self.queue = deque()
# 将非空数组及其初始下标加入队列
for arr in [v1, v2]:
if arr: self.queue.append((arr, 0))
def next(self) -> int:
val = None
# 从队首取出当前数组和下标
arr, idx = self.queue.popleft()
# 获取当前元素
val = arr[idx]
# 将下标加 1
idx += 1
# 如果更新后的下标没有超出数组范围，将新元组加入队尾
if idx < len(arr):
self.queue.append((arr, idx))
return val
def hasNext(self) -> bool:
# 遍历队列中的所有元组，判断是否存在还未迭代完的数组
for arr, idx in self.queue:
if idx < len(arr):
return True
return False
# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())
Explore
在锯齿迭代器的设计中，使用`deque`（双端队列）是因为它支持从两端高效地添加和删除元素。当使用列表时，从列表的开头删除元素的时间复杂度为O(n)，因为需要移动其他所有元素。而在链表中，虽然添加和删除操作的时间复杂度为O(1)，但链表在随机访问时不如`deque`高效。`deque`提供了平衡的方案，即支持快速的随机访问以及从两端高效的插入和删除，这适合锯齿迭代器中经常进行的操作。
是的，如果输入的数组长度不同，按照当前的实现，较短的数组可能会比较长的数组先迭代完成。为了处理这种情况并保持锯齿形的迭代，可以在迭代过程中动态调整各个数组元素的取出顺序。具体地，可以在元素取出后立即将其（如果仍有剩余元素）放回队列，这样可以确保在所有数组中都尽可能均匀地进行迭代。
在`next`方法中，当当前数组已迭代完成，实际上我们是直接丢弃队列中的这个元组，而不是再次加入队列。这种设计的优点是保持了队列的简洁性，只有未完全迭代的数组才保留在队列中，这有助于减少无效的检查和操作。缺点可能是需要在每次调用`next`时进行条件检查，但这是管理动态数据集的必要操作，以确保不会访问已经迭代完毕的数组。
在`hasNext`方法中遍历队列确实可能影响性能，特别是当队列较大时。为了优化这个方法，可以考虑使用一个标志来跟踪是否还有更多的元素可以迭代。每次调用`next`时，如果发现数组已迭代完毕，则更新这个标志。这样，`hasNext`就可以直接返回这个标志的状态，从而避免每次都遍历队列。这个方法可以显著减少在元素接近尾部时的计算量。