难度: Medium
原题连接
内容描述
Given two 1d vectors, implement an iterator to return their elements alternately.
Example:
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].
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:
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:
Input:
[1,2,3]
[4,5,6,7]
[8,9]
Output: [1,4,8,2,5,9,3,6,7].
思路 1 - 时间复杂度: O(1) next + O(1) hasNext- 空间复杂度: O(len(v1) + len(v2))******
双指针, beats 79.91%
class ZigzagIterator(object):
def __init__(self, v1, v2):
"""
Initialize your data structure here.
:type v1: List[int]
:type v2: List[int]
"""
self.v = collections.deque()
i, j = 0, 0
idx = 0
while i < len(v1) and j < len(v2):
if idx % 2 == 0:
self.v.append(v1[i])
i += 1
else:
self.v.append(v2[j])
j += 1
idx += 1
self.v.extend(v1[i:])
self.v.extend(v2[j:])
def next(self):
"""
:rtype: int
"""
return self.v.popleft()
def hasNext(self):
"""
:rtype: bool
"""
return self.v思路 2 - 时间复杂度: O(1) next + O(1) hasNext- 空间复杂度: O(len(v1) + len(v2))******
模拟循环队列，每次取完第一个vector里面的元素之后把它append到最后去，beats 98.63%
class ZigzagIterator(object):
def __init__(self, v1, v2):
"""
Initialize your data structure here.
:type v1: List[int]
:type v2: List[int]
"""
self.q = collections.deque()
if len(v1) != 0:
self.q.append(v1[::-1])
if len(v2) != 0:
self.q.append(v2[::-1])
def next(self):
"""
:rtype: int
"""
if self.hasNext():
v = self.q.popleft()
val = v.pop()
if len(v) != 0:
self.q.append(v)
return val
def hasNext(self):
"""
:rtype: bool
"""
return self.q思路 3 - 时间复杂度: O(1) next + O(1) hasNext- 空间复杂度: O(1)******
参考智慧巅峰
使用iters可以不用消耗extra space
class ZigzagIterator(object):
def __init__(self, v1, v2):
"""
Initialize your data structure here.
:type v1: List[int]
:type v2: List[int]
"""
self.data = [(len(v), iter(v)) for v in (v1, v2) if v]
def next(self):
"""
:rtype: int
"""
len, iter = self.data.pop(0)
if len > 1:
self.data.append((len-1, iter))
return next(iter) # 注意这里调用的是 built-in 函数
def hasNext(self):
"""
:rtype: bool
"""
return self.data或者可以用itertools.count()
class ZigzagIterator(object):
def __init__(self, v1, v2):
"""
Initialize your data structure here.
:type v1: List[int]
:type v2: List[int]
"""
def helper():
for i in itertools.count():
for v in v1, v2:
if i < len(v):
yield v[i]
self.vals = helper()
self.n = len(v1) + len(v2)
def next(self):
"""
:rtype: int
"""
self.n -= 1
return next(self.vals)
def hasNext(self):
"""
:rtype: bool
"""
return self.nWhat if you are given k 1d vectors? How well can your code be extended to such cases?
思路 1 - 时间复杂度: O(1) next + O(1) hasNext- 空间复杂度: O(1)******
上面的思路中好几个都是 compatiable with k vectors
import itertools
class ZigzagIterator(object):
def __init__(self, vectors):
"""
Initialize your data structure here.
:type v1: List[int]
:type v2: List[int]
"""
def helper():
for i in itertools.count():
for v in vectors:
if i < len(v):
yield v[i]
self.vals = helper()
self.n = sum(len(v) for v in vectors)
def next(self):
"""
:rtype: int
"""
self.n -= 1
return next(self.vals)
def hasNext(self):
"""
:rtype: bool
"""
return self.n
s = ZigzagIterator([[1,2,3],[4,5,6,7],[8,9]])
res = []
for i in range(9):
res.append(s.next())
print(res)
output:
[1, 4, 8, 2, 5, 9, 3, 6, 7]