s****r
发帖数: 28 | 1 大家有什么思路么？
How would you define a data structure that stores a set of values (i.e., a
value cannot appear more than one time), and implements the following
functions:
add(p)--adds the value p to the set
delete(p)--removes the value p from the set
getrandom()--returns a random value from the set (all items should be
equally likely). (Assume you have access to some nice random() function.) |
j*****y
发帖数: 1071 | 2 red-black tree/order statistics tree 可以吗？
【在 s****r 的大作中提到】
: 大家有什么思路么？
: How would you define a data structure that stores a set of values (i.e., a
: value cannot appear more than one time), and implements the following
: functions:
: add(p)--adds the value p to the set
: delete(p)--removes the value p from the set
: getrandom()--returns a random value from the set (all items should be
: equally likely). (Assume you have access to some nice random() function.)
|
t*********h
发帖数: 941 | 3 why not hashset directly
【在 s****r 的大作中提到】
: 大家有什么思路么？
: How would you define a data structure that stores a set of values (i.e., a
: value cannot appear more than one time), and implements the following
: functions:
: add(p)--adds the value p to the set
: delete(p)--removes the value p from the set
: getrandom()--returns a random value from the set (all items should be
: equally likely). (Assume you have access to some nice random() function.)
|
s****r
发帖数: 28 | 4 then how to do random output ?
【在 t*********h 的大作中提到】
: why not hashset directly
|
b******t
发帖数: 965 | 5 linkedhashset?
【在 t*********h 的大作中提到】
: why not hashset directly
|
p*****2
发帖数: 21240 | |
f*****7
发帖数: 92 | 7 BST可以嘛？
add，delete就是常规操作
getRandom，就用蓄水池抽样，inorder一次 |
f*****e
发帖数: 2992 | 8 怎么感觉见过很多遍的样子。
【在 s****r 的大作中提到】
: 大家有什么思路么？
: How would you define a data structure that stores a set of values (i.e., a
: value cannot appear more than one time), and implements the following
: functions:
: add(p)--adds the value p to the set
: delete(p)--removes the value p from the set
: getrandom()--returns a random value from the set (all items should be
: equally likely). (Assume you have access to some nice random() function.)
|
|
p*****2
发帖数: 21240 | |
f*****e
发帖数: 2992 | |
|
|
s****r
发帖数: 28 | 11 nb. delete 做的很赞
【在 p*****2 的大作中提到】
: http://blog.sina.com.cn/s/blog_b9285de20101gwnn.html
: 刚写了一个，放在了博客上边。
|
t*********h
发帖数: 941 | 12 i mean implement it like hashset by using a hashmap. since you have access
to buckets, its trivial to return a random item
【在 s****r 的大作中提到】
: then how to do random output ?
|
p*****2
发帖数: 21240 | 13
getrandom的复杂度应该是O（1）的，虽然LZ忘记说明了。
【在 t*********h 的大作中提到】
: i mean implement it like hashset by using a hashmap. since you have access
: to buckets, its trivial to return a random item
|
w*******y
发帖数: 85 | 14 面过。
Array + hash map
Map 中key是p, value 是数组index.
Delete的时候稍微tricky点。
所有操作o(1) |
h*********o
发帖数: 230 | 15 yes
【在 b******t 的大作中提到】
: linkedhashset?
|
O******i
发帖数: 269 | 16 思路是不是这样？
首先想到用数组
取随机，O(1)得到随机的下标
插入，总在尾部，也就是STL vector的push_back, O(1)，如果剩余空间足够大
删除，分两步。
第一步是查找，正常情况下要O(n)的从头开始依次找到位置，所以要配合一个hash表，
O(1)直接得到位置。这个类似hash + DLL实现LRU cache的思路
第二步是删除，正常情况下要O(n)移动所有后续元素向前一步来填补删除后的gap。但
是，参考用无序数组实现优先队列的trick: DelMin()找到最小的也就是优先级最高的
那个元素，删除它然后返回该元素的值。但删除操作无须移动元素，只要把最后一个元
素和它交换，然后数组大小shrink 1。
【在 p*****2 的大作中提到】
: http://blog.sina.com.cn/s/blog_b9285de20101gwnn.html
: 刚写了一个，放在了博客上边。
|
