4 ms·
First, put all items into an array, computing a number k for each item, where k=(sum of all weights above it). Then, just generate a random number 0<x<(sum of
by drcode 18y ago
First, put all items into an array, computing a number k for each item, where k=(sum of all weights above it).
Then, just generate a random number 0<x<(sum of all weights).
Finally, do a binary search on the array O(log(n)) comparing x to k.
...As for the "updating" step, you didn't define that very well or state whether you're interested in minimizing that as well- But given that the number of items may be as large as N it seems that a naive linear update would be the best you could achieve.
- deleted 18y ago[deleted]
- loicfevrier 18y agoBut you will need to re-compute the sum each time you are doing an update wich takes O(n). You can use Binary Indexed Trees to do that efficiently : http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees http://www.topcoder.com/tc?module=Static&d1=tutorials...
- bravura 18y agoIt appears that Binary Indexed Trees are appropriate only when the weights are integral?
- loicfevrier 18y agoExact, I forgot that point.