l**h
发帖数: 893 | 1 print elements in the list in the reversed order efficiently:
void printInReverseOrder(List values) {}
what's the complexity? |
c*****a
发帖数: 808 | |
p*****2
发帖数: 21240 | 3
怎么感觉倒着print就可以了？难道我没理解题目
【在 c*****a 的大作中提到】
: DFS到最后然后print
|
r**h
发帖数: 1288 | 4 递归就好了啊
【在 l**h 的大作中提到】
: print elements in the list in the reversed order efficiently:
: void printInReverseOrder(List values) {}
: what's the complexity?
|
c*****a
发帖数: 808 | 5 这个不算dfs吗
printInReverseOrder( listnode node){
if(node==null) return
printInReverseOrder(node.next)
print(node.val)
} |
p*****2
发帖数: 21240 | 6
题目没说是likedlist呀
【在 c*****a 的大作中提到】
: 这个不算dfs吗
: printInReverseOrder( listnode node){
: if(node==null) return
: printInReverseOrder(node.next)
: print(node.val)
: }
|
c*****a
发帖数: 808 | 7 如果用java list interface，我只懂arraylist, linkedlist
如果arraylist就跟array没区别
linkedlist的话，不清楚是什么implementation,doubly/singly? |
p*****2
发帖数: 21240 | 8
double的。
【在 c*****a 的大作中提到】
: 如果用java list interface，我只懂arraylist, linkedlist
: 如果arraylist就跟array没区别
: linkedlist的话，不清楚是什么implementation,doubly/singly?
|
c*****a
发帖数: 808 | |
j**7
发帖数: 143 | 10
O(n)
void printInReverseOrder(List values)
{
for(int i=values.size()-1;i>=0;i--)
{
System.out.println(values.get(i));
}
}
【在 l**h 的大作中提到】
: print elements in the list in the reversed order efficiently:
: void printInReverseOrder(List values) {}
: what's the complexity?
|
|
|
l**h
发帖数: 893 | 11 这个就是要考的点，因为传的是List,implementation可能是ArrayList,也可能是一个
自己实现的single linked list, 你不能假设 get(i)是O(1).
【在 j**7 的大作中提到】
:
: O(n)
: void printInReverseOrder(List values)
: {
: for(int i=values.size()-1;i>=0;i--)
: {
: System.out.println(values.get(i));
: }
: }
|
j**7
发帖数: 143 | 12
我以为List只能是ArrayList.
【在 l**h 的大作中提到】
: 这个就是要考的点，因为传的是List,implementation可能是ArrayList,也可能是一个
: 自己实现的single linked list, 你不能假设 get(i)是O(1).
|
p*****2
发帖数: 21240 | 13
不过linkedlist也可以做到O(n)。
【在 l**h 的大作中提到】
: 这个就是要考的点，因为传的是List,implementation可能是ArrayList,也可能是一个
: 自己实现的single linked list, 你不能假设 get(i)是O(1).
|
g**e
发帖数: 6127 | 14 space也要O(n)了吧
【在 p*****2 的大作中提到】
:
: 不过linkedlist也可以做到O(n)。
|
p*****2
发帖数: 21240 | 15
不需要
【在 g**e 的大作中提到】
: space也要O(n)了吧
|
c********t
发帖数: 5706 | 16 嗯，dfs肯定要O(n) space. 感觉还不如干脆 toArray()
弱问一下java LinkedList get(i)的 time complexity 是O(n)吧？那size()呢？
【在 g**e 的大作中提到】
: space也要O(n)了吧
|
g**e
发帖数: 6127 | 17 求大牛指点O(1)算法。用iterator递归也算O(n) space的...
【在 p*****2 的大作中提到】
:
: 不需要
|
p*****2
发帖数: 21240 | 18
不是O（1），是O（n）呀。
【在 g**e 的大作中提到】
: 求大牛指点O(1)算法。用iterator递归也算O(n) space的...
|
g**e
发帖数: 6127 | 19 source code写的很清楚
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/
【在 c********t 的大作中提到】
: 嗯，dfs肯定要O(n) space. 感觉还不如干脆 toArray()
: 弱问一下java LinkedList get(i)的 time complexity 是O(n)吧？那size()呢？
|
g**e
发帖数: 6127 | 20 我是说O(1) space O(n) time的方法
【在 p*****2 的大作中提到】
:
: 不是O（1），是O（n）呀。
|
|
|
p*****2
发帖数: 21240 | 21
先reverse一下就可以了
【在 g**e 的大作中提到】
: 我是说O(1) space O(n) time的方法
|
g**e
发帖数: 6127 | 22 只给你List interface咋O(1) space reverse
【在 p*****2 的大作中提到】
:
: 先reverse一下就可以了
|
c********t
发帖数: 5706 | 23 我感觉没有general的O(1) space写法，但实际上无论api里arraylist, linkedlist,还
是用户自己定义single or double linkedlist, 都可以做到O(1) space.
【在 g**e 的大作中提到】
: 我是说O(1) space O(n) time的方法
|
p*****2
发帖数: 21240 | 24
能是ArrayList,也可能是一个
【在 g**e 的大作中提到】
: 只给你List interface咋O(1) space reverse
|
c*****a
发帖数: 808 | 25 Collestions.reverse(list)是多少空间啊 |
