一个单向链表中的随机数,该如何处理

发布时间： 2012-05-09 12:13:59 作者： rapoo

一个单向链表中的随机数
一个单向链表，随机取其中的n个数。有没有人分析下算法？

[解决办法]

探讨

引用:
引用:
替换N个中的哪一个呢？

n个中随机挑选一个。

这样真的保证最后的N个数是随机的嘛？

那可不可以简化点，
1. 一开始选N个，
2. 对后面的每个，分别测试以1/x的概率是否可以替换这N个（第1个开始，直到第N个，然后再从第1个开始，以此类推）。