m****r
发帖数: 141 | 1 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 |
l******n
发帖数: 9344 | 2 hashtable
O(
【在 m****r 的大作中提到】
: 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
|
m****r
发帖数: 141 | 3 It is O(1) space ?
【在 l******n 的大作中提到】
: hashtable
:
: O(
|
o****g
发帖数: 314 | 4 hashtable 沒法 O(1) space 吧？
【在 l******n 的大作中提到】
: hashtable
:
: O(
|
r*********n
发帖数: 4553 | |
l******n
发帖数: 9344 | 6 我以为hash的不算...
那肯定要O(n) space,比如全部元素不同没有重复的情形
【在 m****r 的大作中提到】
: It is O(1) space ?
|
z*****u
发帖数: 3010 | 7 用bloom filter 可以实现
但是不能够保证完全正确~~ |
m****r
发帖数: 141 | 8 Could you please introduce how to use bloom filter to do it ?
Thanks !
【在 z*****u 的大作中提到】
: 用bloom filter 可以实现
: 但是不能够保证完全正确~~
|
S*******s
发帖数: 13043 | 9 是不是O（n）时间怎么做，O(1)空间怎么做，而不是两个同时要满足呀 |
l*******s
发帖数: 1258 | 10 我来个纯属搞笑的算法：
还是基于hashset的。只不过一开始建立hash时，直接把容量最大化，就是达到OS或者
内存的上限。那么不管你的input多大，hashset的空间大小都是不变的，所以空间复杂
度是是O(1).
--Dishes Map，基于餐馆Review的美食发现引擎
https://play.google.com/store/apps/details?id=dishesmap.mobile |
|
|
l*******s
发帖数: 1258 | 11 我来个纯属搞笑的算法：
还是基于hashset的。只不过一开始建立hash时，直接把容量最大化，就是达到OS或者
内存的上限。那么不管你的input多大，hashset的空间大小都是不变的，所以空间复杂
度是是O(1).
--Dishes Map，基于餐馆Review的美食发现引擎
https://play.google.com/store/apps/details?id=dishesmap.mobile |
S*******s
发帖数: 13043 | 12 这个就是counting sort. 空间取决于值域大小，的确是一个常数。
【在 l*******s 的大作中提到】
: 我来个纯属搞笑的算法：
: 还是基于hashset的。只不过一开始建立hash时，直接把容量最大化，就是达到OS或者
: 内存的上限。那么不管你的input多大，hashset的空间大小都是不变的，所以空间复杂
: 度是是O(1).
: --Dishes Map，基于餐馆Review的美食发现引擎
: https://play.google.com/store/apps/details?id=dishesmap.mobile
|
z*****u
发帖数: 3010 | 13 第一次loop的时候
用bloom filter来记录这个元素是否出现过
如果重复出现了，记录在第二个bloom filter上面
第二次loop的时候，跟第二个bloom filter进行比较，如果出现在第二个bloom filter
上面 就删除
两次loop O（2n）
两个bloom filter O（2）
但是存在一定的概率 某个元素没有重复出现 也有可能被删除 |
m****r
发帖数: 141 | 14 Ok,
About the size of bloom filter, if the link list has 100 billion elements
and each element is 8 bytes, what is the exact size of bloom filter ?
thanks !
filter
【在 z*****u 的大作中提到】
: 第一次loop的时候
: 用bloom filter来记录这个元素是否出现过
: 如果重复出现了，记录在第二个bloom filter上面
: 第二次loop的时候，跟第二个bloom filter进行比较，如果出现在第二个bloom filter
: 上面 就删除
: 两次loop O（2n）
: 两个bloom filter O（2）
: 但是存在一定的概率 某个元素没有重复出现 也有可能被删除
|
b*******s
发帖数: 5216 | 15 我觉得你们对空间复杂度的理解都和我学的很不一样
filter
【在 z*****u 的大作中提到】
: 第一次loop的时候
: 用bloom filter来记录这个元素是否出现过
: 如果重复出现了，记录在第二个bloom filter上面
: 第二次loop的时候，跟第二个bloom filter进行比较，如果出现在第二个bloom filter
: 上面 就删除
: 两次loop O（2n）
: 两个bloom filter O（2）
: 但是存在一定的概率 某个元素没有重复出现 也有可能被删除
|
f******n
发帖数: 346 | 16 O(1)就是意味着跟数据输入的规模无关，是个常量吧。
应该是counting sort，先找最大最小值，然后再建一个相应的数组存对应数值出现的
频率。
更简单的版本是先限定是ASCII字符，然后建一个固定容量的map.
【在 S*******s 的大作中提到】
: 这个就是counting sort. 空间取决于值域大小，的确是一个常数。
|
