3 ms·
It was not a requirement :) However it won't get slow, it's O(1) to lookup if a key exists.
by tiborsaas 7y ago
It was not a requirement :) However it won't get slow, it's O(1) to lookup if a key exists.
- kadoban 7y agoIt will get slow towards the end once each loop iteration has a very low chance of being productive (only happens when you're choosing all or almost all elements). You can fix that, though there's potential tradeoffs.
- andreareina 7y ago> (Stated more formally: given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n. We reasonably ask that this be done in O(k) time and O(1) additional space. Finally, the distribution must be uniform.) As k approaches n the expected number of draws needed to get k unique values increases faster than O(k).
- deleted 7y ago[deleted]