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的解法啊。那个方法就是cc150里的,时间复杂度是
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) 怎么这么高级啊 |