Блог пользователя Sakalya

Random Numbers
Автор Sakalya, 12 лет назад, По-английски
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..
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 :)

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Do random shuffle in O(n) then select first m integers.
→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

while (i<m)
{
   1) choose a random number(0..n-1)
   2) add a[random] to your set
   3) swap (a[random], a[n-1])
   4) n--, i++
}

This should take O(m)

→ Ответить