p******d
发帖数: 63 | 1 Reverse an immutable singly linked list in O(n) time with O(logn) space.
我只能想到时间O(nlogn)空间O(logn)的解法。 |
s********x
发帖数: 81 | 2 看不懂题目，immutable的具体定义是什么? |
g*********e
发帖数: 14401 | 3 题目有误
【在 p******d 的大作中提到】
: Reverse an immutable singly linked list in O(n) time with O(logn) space.
: 我只能想到时间O(nlogn)空间O(logn)的解法。
|
h**p
发帖数: 211 | |
l******s
发帖数: 3045 | 5 recursive + divide and conquer and this should satisfy the 2 complexity.
【在 p******d 的大作中提到】
: Reverse an immutable singly linked list in O(n) time with O(logn) space.
: 我只能想到时间O(nlogn)空间O(logn)的解法。
|
c***u
发帖数: 4107 | 6 reverse link难道不是在O(n) time complexity 和 O(1) space 就可以了吗?
为什么还需要O(logN) space. |
C******h
发帖数: 786 | 7 const ?
【在 s********x 的大作中提到】
: 看不懂题目，immutable的具体定义是什么?
|
C******h
发帖数: 786 | 8 好像cc150 有类似题
【在 c***u 的大作中提到】
: reverse link难道不是在O(n) time complexity 和 O(1) space 就可以了吗?
: 为什么还需要O(logN) space.
|
s****3
发帖数: 270 | 9
这个前提必须每个node 是都是unique吧? 否则你没办法divide and conquer 然后time
complexisty 只有o(n)
【在 l******s 的大作中提到】
: recursive + divide and conquer and this should satisfy the 2 complexity.
|
l******s
发帖数: 3045 | 10 这是做reverse，不需要比较不用管具体值。具体做法就是用单步双步指针，找到中间
node后将前后段list reverse，同时递归做前半段和后半段。
time
【在 s****3 的大作中提到】
:
: 这个前提必须每个node 是都是unique吧? 否则你没办法divide and conquer 然后time
: complexisty 只有o(n)
|
|
|
T****U
发帖数: 3344 | 11 这题重点是immutable, 感觉题目有问题
【在 l******s 的大作中提到】
: 这是做reverse，不需要比较不用管具体值。具体做法就是用单步双步指针，找到中间
: node后将前后段list reverse，同时递归做前半段和后半段。
:
: time
|
l******s
发帖数: 3045 | 12 就是指list里所属的所有node在内存中的位置和值以及list的整体长度没有任何变化就
行了吧，如果我理解正确只是为了避免改值的解法。
【在 T****U 的大作中提到】
: 这题重点是immutable, 感觉题目有问题
|
w*******g
发帖数: 9932 | 13 okay
you need to know the end of the list and the one before it and so forth and
so on
the problem is you can't reverse pointer as you traverse the list so each
time you need to traverse the entire list to get to the end
you have to use a tree like data structure to keep track of your position as
you traverse and invert the list.
since you only need to know the path from root to the current element you
are on, you need log space. it's linear time since you only need two passes
【在 p******d 的大作中提到】
: Reverse an immutable singly linked list in O(n) time with O(logn) space.
: 我只能想到时间O(nlogn)空间O(logn)的解法。
|
m****t
发帖数: 23 | 14 还是不明白。这个题和leetcode reverse linked list有深摸区别？
到底是深摸不能变？如果node的pointer不可以变，怎摸reverse linked list?
似乎是pointer不可变，但value可以变。please clarify |
m****t
发帖数: 23 | 15 @wildThing
What do you mean by tree data structure? also what do you mean by " the path
from root to the current element"?
sorry I can not understand |
f*****e
发帖数: 2992 | 16 就像章鱼的脚。一前一后。
logn个指针指向n-1, n-2,n-4,n-8,....
先1和n-1做。做完之后，n-1就可以腾出来了，插入n－2。
【在 p******d 的大作中提到】
: Reverse an immutable singly linked list in O(n) time with O(logn) space.
: 我只能想到时间O(nlogn)空间O(logn)的解法。
|
e********2
发帖数: 495 | 17 我觉得O(sqrt(N))space，才可能有O(N)时间的解。
【在 f*****e 的大作中提到】
: 就像章鱼的脚。一前一后。
: logn个指针指向n-1, n-2,n-4,n-8,....
: 先1和n-1做。做完之后，n-1就可以腾出来了，插入n－2。
|
m****t
发帖数: 23 | 18 @fatalme
能不能给个提示如何实现这个“章鱼脚”
似乎找到这些logn指证需要nlogn时间 |
f*****e
发帖数: 2992 | 19 想想也是，看来只能O(N^1/3))space complexity了, O(N)时间了。这个应该挺简单。
【在 m****t 的大作中提到】
: @fatalme
: 能不能给个提示如何实现这个“章鱼脚”
: 似乎找到这些logn指证需要nlogn时间
|
m****t
发帖数: 23 | 20 能给个提示如何实现这个O(N^1/3))space complexity吗？
我只能想到Ｏ(ｎｌｏｇｎ)时间的算法 |
|
|
f*****e
发帖数: 2992 | 21 假设数组元素有N个，有n个指针
看用下面的这个方法和n个指针能和右边互换的元素有多少个：
n个指针从左到右，第一个与第二个相隔n － 1个位置，第二个与第三个相隔n - 2个位
置，倒数第二个和倒数第一个相隔2个位置。
那么可以与右半边N/2的元素互换的元素有N1=n(n+1)/2个，时间O(N1)：
从最后一个指针开始，用完之后，和前面一个指针一起互换下一段。
我们把右半边的元素分成N/2/(N1)段，用N/2/N1个指针标记起来。
那么需要的指针要n + N/2/N1个, that is n + N/(n(n+1))，然后做最小化，得到n~O(
N^1/3)。时间O(N)
【在 m****t 的大作中提到】
: 能给个提示如何实现这个O(N^1/3))space complexity吗？
: 我只能想到Ｏ(ｎｌｏｇｎ)时间的算法
|
r*******g
发帖数: 1335 | 22 那依然是可以O(n)时间O(1) space做出来啊，到底题目什么意思？
【在 l******s 的大作中提到】
: 就是指list里所属的所有node在内存中的位置和值以及list的整体长度没有任何变化就
: 行了吧，如果我理解正确只是为了避免改值的解法。
|
e********2
发帖数: 495 | 23 除了指针都可以改。
【在 r*******g 的大作中提到】
: 那依然是可以O(n)时间O(1) space做出来啊，到底题目什么意思？
|
r*******g
发帖数: 1335 | 24 ic, 原来是可以改数值但是不能改指针
看来就是分治了。
【在 e********2 的大作中提到】
: 除了指针都可以改。
|
