m***h
发帖数: 489 | 1 假如你的朋友信息用hash表来存储，姓名是key，现在想随机挑选一人。朋友表是动态
增减的。 我当时没想出来。 |
b*****u
发帖数: 648 | 2 额外搞一个vector，然后取随机index ？ |
m***h
发帖数: 489 | 3 maintain这个vector也要O(n)的时间吧。
【在 b*****u 的大作中提到】
: 额外搞一个vector，然后取随机index ？
|
d**********x
发帖数: 4083 | 4 不需要
只要额外维护一个vector，然后双向引用就行了
删除O(1)，添加均摊O(1)
【在 m***h 的大作中提到】
: maintain这个vector也要O(n)的时间吧。
|
b*****u
发帖数: 648 | 5 如果就一次确实没差，相对于多次操作来说是可以忽略的。
【在 m***h 的大作中提到】
: maintain这个vector也要O(n)的时间吧。
|
h****n
发帖数: 1093 | 6 suppose the hash is implemented by chaining
Hash size is m, key number is n, the longest length of chain is L
Then we can do:
1. randomly select a bucket, suppose the length of chain is k (1<=k<=L)
2. for the list in bucket k, randomly generate a number l between 1 to L
if l is less than k, then we return the lth item in the list
It is just like a rejection sampling in a 2D array
Time complexity: The expected number per bucket is n/m
The probability that rejection sampling succeeds is n/m/L
The expected attempt times will be L*m/n along with O(L) for retrieving that
item
The average time complexity will be O(L(1+m/n))
In the worst case L will be n
Then the worst case will be O(n+m)
【在 m***h 的大作中提到】
: 假如你的朋友信息用hash表来存储，姓名是key，现在想随机挑选一人。朋友表是动态
: 增减的。 我当时没想出来。
|
h****n
发帖数: 1093 | 7 what about the worst case that all the key are inserted into the same index?
【在 b*****u 的大作中提到】
: 额外搞一个vector，然后取随机index ？
|
d**********x
发帖数: 4083 | 8 所以要用每个元素的直接ref，而非key。
index?
【在 h****n 的大作中提到】
: what about the worst case that all the key are inserted into the same index?
|
h****n
发帖数: 1093 | 9 vector的删除可不止O（1）,你要把所有后面的元素往前挪的
【在 d**********x 的大作中提到】
: 不需要
: 只要额外维护一个vector，然后双向引用就行了
: 删除O(1)，添加均摊O(1)
|
d**********x
发帖数: 4083 | 10 圡了不是
将当前元素与最后一个swap，然后size减1.
【在 h****n 的大作中提到】
: vector的删除可不止O（1）,你要把所有后面的元素往前挪的
|
h****n
发帖数: 1093 | 11 好吧。这里的case不需要保持原来的顺序
【在 d**********x 的大作中提到】
: 圡了不是
: 将当前元素与最后一个swap，然后size减1.
|
C***U
发帖数: 2406 | 12 楼上的说的对
这个题目可以用一个额外的array来实现
【在 m***h 的大作中提到】
: 假如你的朋友信息用hash表来存储，姓名是key，现在想随机挑选一人。朋友表是动态
: 增减的。 我当时没想出来。
|
m***h
发帖数: 489 | 13 动态的，如何用array？而且随机要均匀。我当时说外部用个linked list存姓名，然后
随机挑名字，但还是O(n)。
【在 C***U 的大作中提到】
: 楼上的说的对
: 这个题目可以用一个额外的array来实现
|
y*******g
发帖数: 6599 | 14 这个不对啊，这个假设了 k是平均的，事实上不一定
that
【在 h****n 的大作中提到】
: suppose the hash is implemented by chaining
: Hash size is m, key number is n, the longest length of chain is L
: Then we can do:
: 1. randomly select a bucket, suppose the length of chain is k (1<=k<=L)
: 2. for the list in bucket k, randomly generate a number l between 1 to L
: if l is less than k, then we return the lth item in the list
: It is just like a rejection sampling in a 2D array
: Time complexity: The expected number per bucket is n/m
: The probability that rejection sampling succeeds is n/m/L
: The expected attempt times will be L*m/n along with O(L) for retrieving that
|
