I need to select k
elements randomly in the range 0 to n-1
. n
can be upto 10^9. And k
can range from 1 to n-1
. I can do this in O(n) time just by shuffling an array containing values 0 to n-1
and choosing first k
elements from it. But when k
is small this method is both time and memory inefficient. Is there any O(k) solution to this problem?
Aucun commentaire:
Enregistrer un commentaire