h****n
发帖数: 1093 | 1 Pick a random number from weighted list based on weight
比如[1,1,4,5]要求以4/11的概率返回4
要求支持动态插入新元素，动态删除新元素
如果不要求动态的话，开一个新的cumulative sum 的array之后做binary search即可
返回相应的元素，但是如果要求支持动态的可能需要用树这种结构
具体怎么弄，还没想清楚，有什么idea吗？ | c*****a
发帖数: 808 | 2 找1是不是 2/11?还是1/11?
arraylist算不算动态啊 | f*****e
发帖数: 2992 | 3 用RBT，key是插入的interval的序号，从0开始。
每个节点代表一个interval，储存左边(or左子树)所有intervals的长度和，然后rand(
)*(sum of all intervals)，落到哪个interval上就是个那个interval。rand()返回一
个0<=x<=1的随机值。删除操作一些细节需要workout，但很简单。
【在 h****n 的大作中提到】
: Pick a random number from weighted list based on weight
: 比如[1,1,4,5]要求以4/11的概率返回4
: 要求支持动态插入新元素，动态删除新元素
: 如果不要求动态的话，开一个新的cumulative sum 的array之后做binary search即可
: 返回相应的元素，但是如果要求支持动态的可能需要用树这种结构
: 具体怎么弄，还没想清楚，有什么idea吗？
| Y********f
发帖数: 410 | 4 插入新元素以后以前元素的概率怎么算？按比例？
比如说[1,2]个50%， 出入新元素3，概率50%, 那之后就是[1,2,3]的概率为25%, 25%,
50%?
【在 h****n 的大作中提到】
: Pick a random number from weighted list based on weight
: 比如[1,1,4,5]要求以4/11的概率返回4
: 要求支持动态插入新元素，动态删除新元素
: 如果不要求动态的话，开一个新的cumulative sum 的array之后做binary search即可
: 返回相应的元素，但是如果要求支持动态的可能需要用树这种结构
: 具体怎么弄，还没想清楚，有什么idea吗？
| h****n
发帖数: 1093 | 5 RBT如果要求coding这个就太坑爹了吧，一个面试题
rand(
【在 f*****e 的大作中提到】
: 用RBT，key是插入的interval的序号，从0开始。
: 每个节点代表一个interval，储存左边(or左子树)所有intervals的长度和，然后rand(
: )*(sum of all intervals)，落到哪个interval上就是个那个interval。rand()返回一
: 个0<=x<=1的随机值。删除操作一些细节需要workout，但很简单。
| p*****2
发帖数: 21240 | 6 [1,1,4,5]要求以4/11的概率返回4
纪录sum 11
随机产生0－10的一个整数
0，1 returns 1
2,3,4,5 returns 4
6,7,8,9,10 returns 5
不过每次操作都是O(n)的复杂度。优化一下可以到log(n) |
|
