3 ms·
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
by TheMerovingian 7y ago
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- Bossle 7y agoExactly, just truncate the iteration to the first k elements. Need a hash table to get the modified values, so it breaks the "O(1) extra space" condition, but that condition is bullshit anyway, you're already using O(k) space to store the numbers you find, an extra hash table is also O(k) space. http://ideone.com/5uwqNO http://ideone.com/5uwqNO
- dahart 7y agoIt’s related to Fisher-Yates shuffle, https://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to_Fisher-Yates_shuffle https://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to... But it’s not the same thing. The difference is whether you can keep all samples in memory at the same time. With Vitter / reservoir sampling, you only need to have your reservoir in memory plus enough space for 1 new sample at a time, so you can stream through a large number of samples with a tiny amount of memory.