w****x
发帖数: 2483 | 1 设计一个集合数据结构(set,只存unique的value)要求
能在O(1)时间内insert，delete，random query(比如目前set中有n个元素，给一个介
于1到n的随机数k，可以在O(1)时间内返回第k个value)
比如：+表示插入，-表示删除
+1+1+3+3+5-3-1+8+1+4
最后的set是{5814}
k=2，返回8 |
f*****e
发帖数: 2992 | 2 不知道下面这个对不对？
CLRS 3rd
11.2-4
【在 w****x 的大作中提到】
: 设计一个集合数据结构(set,只存unique的value)要求
: 能在O(1)时间内insert，delete，random query(比如目前set中有n个元素，给一个介
: 于1到n的随机数k，可以在O(1)时间内返回第k个value)
: 比如：+表示插入，-表示删除
: +1+1+3+3+5-3-1+8+1+4
: 最后的set是{5814}
: k=2，返回8
|
w****x
发帖数: 2483 | 3
没见
【在 f*****e 的大作中提到】
: 不知道下面这个对不对？
: CLRS 3rd
: 11.2-4
|
f*****e
发帖数: 2992 | 4 习题11.2-4啊。
【在 w****x 的大作中提到】
:
: 没见
|
a*******y
发帖数: 1040 | 5 这个难道用个hashtable 和一个array不就行了吗？
hashtable 存(value, index in array) |
w****x
发帖数: 2483 | 6
没说要random access啊
【在 f*****e 的大作中提到】
: 习题11.2-4啊。
|
w****x
发帖数: 2483 | 7
不行啊， 删除一个所有后面的index都要减小一个
【在 a*******y 的大作中提到】
: 这个难道用个hashtable 和一个array不就行了吗？
: hashtable 存(value, index in array)
|
a*******y
发帖数: 1040 | 8 No 啊，
after delete，你move the last element into this empty shit pot, and change
the index for the last element.
【在 w****x 的大作中提到】
:
: 不行啊， 删除一个所有后面的index都要减小一个
|
w****x
发帖数: 2483 | 9
那你random access就不对了
【在 a*******y 的大作中提到】
: No 啊，
: after delete，你move the last element into this empty shit pot, and change
: the index for the last element.
|
a***o
发帖数: 1182 | 10 你这个例子他是对的，但是比如A[]= 1,2,3,4,5
delete （2） 然后get(A[1])还要返回3就不行了，只能返回5，不过本来就是random，
返回3，返回5意义不大
【在 w****x 的大作中提到】
:
: 那你random access就不对了
|
|
|
t*********7
发帖数: 255 | 11 HashMap + Array吧,想法跟楼上那个哥们差不多,
不同就是记录一下delCount,楼主你那个例子删除了2个元素,那最后要找K=2,就等于2+2
=4第四个放进数组的元素也就是8...这样一直用ARRAY记录,等ARRAY快满的时候就重置
ARRAY,并且delCount=0,假如空间还不够就COPY ARRAY去一个更大的ARRAY空间...不知
道这样行不行... |
w****x
发帖数: 2483 | 12
+2
这样不对啊， 要是+0+1+1+3+4-1 ==> 034 现在取第一个应该还是0, 你的逻辑就是3了
【在 t*********7 的大作中提到】
: HashMap + Array吧,想法跟楼上那个哥们差不多,
: 不同就是记录一下delCount,楼主你那个例子删除了2个元素,那最后要找K=2,就等于2+2
: =4第四个放进数组的元素也就是8...这样一直用ARRAY记录,等ARRAY快满的时候就重置
: ARRAY,并且delCount=0,假如空间还不够就COPY ARRAY去一个更大的ARRAY空间...不知
: 道这样行不行...
|
f*****e
发帖数: 2992 | 13 我觉得random access应为getRandomElement，你题目看错了，或者理解错了。
【在 w****x 的大作中提到】
:
: +2
: 这样不对啊， 要是+0+1+1+3+4-1 ==> 034 现在取第一个应该还是0, 你的逻辑就是3了
|
w****x
发帖数: 2483 | 14
哦， 可能是这样， 这样就简单了....
【在 f*****e 的大作中提到】
: 我觉得random access应为getRandomElement，你题目看错了，或者理解错了。
|
h*****3
发帖数: 1391 | 15 唉，我有次电话面试就是这题。
能不能这样：
一个array + hash+queque，queque里面放avaiable index，如果删除以后，index 可
以回收到queque里面。通过hash可以random access了。 |
z****e
发帖数: 9 | 16 How about this:
Use one global counter and two HashMap
counter will be increased by 1 when insert one value.
HashMap to save value and it's counter as index.
Another HashMap to save the index and its value.
When delete, both the value-index pair and index-value pair removed from the
hashmap.
when random access with one index, check whether the value is existed in the
second hashmap as key, if not, increase the index by 1 and continue to find
it in the hashmap, until the index == counter, which means no value found
and return null.
insert and delete with O(1) time, cannot prove random access with O(1) time. |
