New answers tagged

0 votes

Weighted sample of ~k elements from array in O(n) time?

Yes, assuming we can assume that all elements are distinct. Here is one approach. Let $x_1,\dots,x_n$ denote the elements and $w_i$ the weight associated to $x_i$. Consider the following algorithm: ...
user avatar
  • 141k

Top 50 recent answers are included