[jonnyba]

if the number of different weights is finite and small, you could create a bucket for each different weight.

for example if the possible weights are .25, .5, and .75, put all items into one of those buckets (array backed). The bucket then gets a weight of (individual weight)*(bucket size). First randomly choose a bucket based on the bucket weight, then randomly choose an object from the bucket.

[gojomo]

Still O(n).