資訊專欄INFORMATION COLUMN
摘要：用變量和取模來(lái)判斷我們?cè)撊×斜碇械牡趲讉€(gè)迭代器。同樣，由于每用完一個(gè)迭代器后都要移出一個(gè)，變量也要相應(yīng)的更新為該迭代器下標(biāo)的上一個(gè)下標(biāo)。如果迭代器列表為空，說(shuō)明沒(méi)有下一個(gè)了。
Zigzag Iterator
雙迭代器 復(fù)雜度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].
時(shí)間 O(N) 空間 O(1)
思路該題實(shí)際上就是輪流取兩個(gè)列表的下一個(gè)元素。我們存下兩個(gè)列表的迭代器，然后用一個(gè)遞增的turns變量和取模的方法來(lái)判斷該取哪一個(gè)列表的元素。
代碼public class ZigzagIterator {
Iterator it1;
Iterator it2;
int turns;
public ZigzagIterator(List v1, List v2) {
this.it1 = v1.iterator();
this.it2 = v2.iterator();
turns = 0;
}
public int next() {
// 如果沒(méi)有下一個(gè)則返回0
if(!hasNext()){
return 0;
}
turns++;
// 如果是第奇數(shù)個(gè)，且第一個(gè)列表也有下一個(gè)元素時(shí)，返回第一個(gè)列表的下一個(gè)
// 如果第二個(gè)列表已經(jīng)沒(méi)有，返回第一個(gè)列表的下一個(gè)
if((turns % 2 == 1 && it1.hasNext()) || (!it2.hasNext())){
return it1.next();
// 如果是第偶數(shù)個(gè)，且第二個(gè)列表也有下一個(gè)元素時(shí)，返回第二個(gè)列表的下一個(gè)
// 如果第一個(gè)列表已經(jīng)沒(méi)有，返回第二個(gè)列表的下一個(gè)
} else if((turns % 2 == 0 && it2.hasNext()) || (!it1.hasNext())){
return it2.next();
}
return 0;
}
public boolean hasNext() {
return it1.hasNext() || it2.hasNext();
}
}
后續(xù) Follow Up
Q：如果輸入是k個(gè)列表呢？
A：使用一個(gè)迭代器的列表來(lái)管理這些迭代器。用turns變量和取模來(lái)判斷我們?cè)撊×斜碇械牡趲讉€(gè)迭代器。不同點(diǎn)在于，一個(gè)迭代器用完后，我們要將其從列表中移出，這樣我們下次就不用再找這個(gè)空的迭代器了。同樣，由于每用完一個(gè)迭代器后都要移出一個(gè)，turns變量也要相應(yīng)的更新為該迭代器下標(biāo)的上一個(gè)下標(biāo)。如果迭代器列表為空，說(shuō)明沒(méi)有下一個(gè)了。
