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) |
|