说我有一个长度数字的链表N.N非常大,我事先并不知道确切的价值N.
如何最有效地编写一个从列表中返回k完全随机数的函数？
你如何在一次通过或不通过两次通过的情况下在链表中选择一个未知长度的统一随机元素？
我有一个方向链表而不知道它的大小.
我想在这个列表中得到一个随机元素,我只有一次机会遍历列表.(我不允许遍历两次或更多次)
这个问题的算法是什么？谢谢!
给定未知长度列表,通过仅扫描一次来返回其中的随机项.
我的想法:
类似的算法是水库采样(由其他人发布).但是,它太复杂了,因为它需要运行rand()并在每次迭代时保持k个节点.
有更好的解决方案吗？O(n)时间和O(1)空间？
我需要从列表中选择一个满足某些条件的随机元素.我一直在使用的方法有效,但我确信并非一切都有效.最有效的方法是什么？
以下代码位于while(true)循环内,因此在每次迭代时显然不是非常有效地对列表进行洗牌.
Foo randomPick = null;
Collections.shuffle(myList);
for (Foo f : myList) {
if (f.property) {
randomPick = f;
break;
}
}
提前致谢!