Sakalya's blog

Random Numbers
By Sakalya, 12 years ago, In English
How can we randomly generate a set of m integers from an array of size n..Each element must have equal probability of being chosen..
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

m times pick random element from array and remove it. To do it in O(N log N), one can use segment tree.

UPD. Oops, my solution looks way overcomplicated :)

→ Reply
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it
Do random shuffle in O(n) then select first m integers.
→ Reply