狗家跪经

crackinterview

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

问了一个shuffle array with weight，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

th weight的最优解法吗？

roosterxie

https://stackoverflow.com/questions/23971365/weighted-randomized-ordering

You have items with weights:
Item A, weight 42
Item B, weight 5
Item C, weight 96
Item D, weight 33
First add up all the weights: 42 + 5 + 96 + 33 = 176
Now pick a random number, r, from 0 up to the sum of the weights: 0 <= r < 176. I have used integers, but you could use reals if required.
Compare r with the ranges defined by the weights:
0 <= r < 42: select item A.
42 <= r < 47 (= 42 + 5): select item B.
47 <= r < 143 (= 47 + 96): select item C.
143 <= r < 176 (= 143 + 33): select item D.
When you have picked the first item, then repeat the process with the three remaining items and a reduced sum of all the weights. Keep repeating until there are no more items to pick.

复制代码

这个应该是最简单的方法了

hychin

啥叫shuff array with weight？解释下？

672347250

就一轮么？

hychin · 2017-12-14 10:24:58

roosterxie 发表于 2017-12-5 13:19
https://stackoverflow.com/questions/23971365/weighted-randomized-ordering

这个应该是最简单的方法 ...

你这个办法是O（n^2）,我研究了下，这个题用二叉树可以做到nlogn

littlegrass · 2017-12-30 05:16:40

hychin 发表于 2017-12-14 10:24
你这个办法是O（n^2）,我研究了下，这个题用二叉树可以做到nlogn

请问下如何用二叉树可以做到nlogn

kaixinNI · 2017-12-31 13:36:21

littlegrass 发表于 2017-12-30 05:16
请问下如何用二叉树可以做到nlogn

你好，想请问怎么用二叉树做到nlogn呢？谢谢！

kaixinNI · 2017-12-31 13:37:29

hychin 发表于 2017-12-14 10:24
你这个办法是O（n^2）,我研究了下，这个题用二叉树可以做到nlogn

你好，想请问怎么用二叉树做到nlogn呢？谢谢！刚才不小心回复错了

IsingModel · 2017-12-31 16:20:09

https://www.quora.com/Is-there-a-simple-O-nlogn-algorithm-for-Weighted-Shuffling-of-cards
可以nlogn 但是得自己建树写起来应该比较麻烦吧

paopaojeffrey

几号面的呀？