3 ms·
your random number function might return the same number multiple times? So to choose k random but unique numbers you may have to call the random number functi
by willvarfar 10mo ago
your random number function might return the same number multiple times? So to choose k random but unique numbers you may have to call the random number function more than k times?
Of course my intuition would be that you can do a random shuffle and then take the first k, which is O(N). So I might be misunderstanding.
- chopin 10mo agoIs there a O(n) shuffling algorithm? In place, I don't think so.
- tialaramex 10mo agoUm, the "Knuth Shuffle" aka "Fisher-Yates" ? https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- minitech 10mo agoYou can do that for O(N), but the problem can be solved in O(k).