题目:
Implement an iterator to flatten a 2d vector.
For example,
Given 2d vector =
[ [1,2], [3], [4,5,6] ]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6]
.
Hint:
x
and y
.x
and y
must always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it?hasNext()
. Which is more complex?Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.
链接: http://leetcode.com/problems/flatten-2d-vector/
题解:
构造一个2D的iterator。不台理解iterator的原理,第一想法是把vec2d里面的元素都读到Queue里 ,然后再逐个读取。这样的话初始化需要O(n), next和hasNext都为O(1),Space Complexity也是O(n),虽然能ac,但是当vec2d足够大的时候会出问题。
Time Complexity - constructor - O(n), hasNext - O(1), next() - O(1), Space Complexity - O(n)。
public class Vector2D { private Queue<Integer> vec1d; public Vector2D(List<List<Integer>> vec2d) { vec1d = new LinkedList<>(); for(List<Integer> list : vec2d) { for(int i : list) { vec1d.offer(i); } } } public int next() { if(hasNext()) return vec1d.poll(); else return Integer.MAX_VALUE; } public boolean hasNext() { return vec1d.size() > 0; } } /** * Your Vector2D object will be instantiated and called as such: * Vector2D i = new Vector2D(vec2d); * while (i.hasNext()) v[f()] = i.next(); */
Reference:
http://web.cse.ohio-state.edu/software/2231/web-sw2/extras/slides/17a.Iterators.pdf
http://docs.oracle.com/javase/7/docs/api/
http://stackoverflow.com/questions/21988341/how-to-iterate-through-two-dimensional-arraylist-using-iterator
http://www.cs.cornell.edu/courses/cs211/2005fa/Lectures/L15-Iterators%20&%20Inner%20Classes/L15cs211fa05.pdf
https://leetcode.com/discuss/50292/7-9-lines-added-java-and-c-o-1-space
https://leetcode.com/discuss/55199/pure-iterator-solution-additional-data-structure-list-get
https://leetcode.com/discuss/57984/simple-and-short-java-solution-with-iterator
https://leetcode.com/discuss/50356/my-concise-java-solution
https://leetcode.com/discuss/68860/java-o-1-space-solution
原文:http://www.cnblogs.com/yrbbest/p/5011857.html