use*_*288 2 c++ random algorithm list data-structures
给定未知长度列表,通过仅扫描一次来返回其中的随机项.
我的想法:
类似的算法是水库采样(由其他人发布).但是,它太复杂了,因为它需要运行rand()并在每次迭代时保持k个节点.
有更好的解决方案吗？O(n)时间和O(1)空间？
你为什么反对水库采样？你碰巧用k = 1做了.有一些小的优化(例如你不需要从k中选择1,因为k = 1)但这是正确的方法.您可以尝试通过一次处理一个固定的窗口进行优化,如果您应该选择窗口中的任何项目而不是您拥有的项目,请以相同的概率进行数学计算,以最小化rand()调用在一个更复杂的算法的昂贵,但无论如何你或多或少会回到水库采样.