给定一个未知长度的列表，通过仅扫描 1 次返回其中的随机项目。
我的想法:
类似的算法是 Reservoir Sampling(其他人发布)。但是，它太复杂了，因为它需要运行 rand() 并在每次迭代中保留 k 个节点。
有更好的解决方案吗？ O(n) 时间和 O(1) 空间？
最佳答案
您为什么反对水库采样？您碰巧是在 k = 1 的情况下进行的。有一些小的优化(例如，您不需要从 k 中选择 1，因为 k = 1)但这是正确的方法。您可以尝试通过一次保持处理一个固定窗口来进行优化，做数学计算以相等的概率计算出您是否应该选择窗口中的任何项目而不是您拥有的项目等，以尽量减少 rand() 调用以更复杂的算法为代价，但无论如何你或多或少都会回到水库采样。
关于c++ - 给定一个未知长度的列表，通过仅扫描 1 次返回其中的随机项目，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8695022/