m****r
发帖数: 141 | 1 【 以下文字转载自 Quant 讨论区 】
发信人: mitcar (mitcar), 信区: Quant
标 题: 去掉单向链表中的重复元素 with O(n) time and O(1)
发信站: BBS 未名空间站 (Mon Aug 19 21:49:27 2013, 美东)
How remove duplicated elements on a single-linked list with O(n) time and O(
1) space ?
The elements can be any characters, numbers and they are not sorted.
For example, given 8 --> 6 --> 7 --> 6 --> 5
return 8 --> 6 --> 7 --> 5
O(1) space seems to be tough ?
Any help would be appreciated !
Thanks |
e*******8
发帖数: 94 | 2 这题应该还有其他假设吧（比如元素范围，或者重复次数之类）？不然，单判断是否有
重复元素已经需要至少n log n的时间了（不用hash的话）。 |
b**********5
发帖数: 7881 | 3 这题是careercup里的吧。 在弄一个runner pointer啊
【在 e*******8 的大作中提到】
: 这题应该还有其他假设吧（比如元素范围，或者重复次数之类）？不然，单判断是否有
: 重复元素已经需要至少n log n的时间了（不用hash的话）。
|
e*******8
发帖数: 94 | 4 恩，我看过那个runner pointer的解法啊。那个方法就是cc１５０里的，时间复杂度是
O(n^2), space complexity O(1). 另外一个解法是用hash table，time complexity O
(n), space complexity O(n)...
【在 b**********5 的大作中提到】
: 这题是careercup里的吧。 在弄一个runner pointer啊
|
r****s
发帖数: 1025 | 5 bitmap不就行了，又没有说什么无限长度之类的。 |
i****y
发帖数: 84 | |
a********m
发帖数: 15480 | 7 估计应该是这样。不然O(n)/O(1)感觉不可能。
【在 e*******8 的大作中提到】
: 这题应该还有其他假设吧（比如元素范围，或者重复次数之类）？不然，单判断是否有
: 重复元素已经需要至少n log n的时间了（不用hash的话）。
|
m****r
发帖数: 141 | 8 Could you please give more details about how to use bitmap for solving this
problem ?
【在 r****s 的大作中提到】
: bitmap不就行了，又没有说什么无限长度之类的。
|
s********r
发帖数: 403 | 9 Quant 区转来的，还以为是要用 Quantum Computing, O(N)/O(1) 怎么这么高级啊 |
