算法在[0,8000]范围内生成1000个不同的整数？

Question

可能重复:
如何有效地生成0和上限N之间的K个非重复整数列表

有什么替代方法可以生成[0,8000]范围内的1000个不同的随机整数,而不是以下方法:

1. 天真的方法:生成一个数字并检查它是否已经在数组中.为O(n ^ 2)
2. 线性shuffle:生成序列0到8000,shuffle,取第1000个.O(n)

Answer 1

您可以使用使用交换实现的部分Fisher-Yates shuffle.此算法的一个很好的功能是,如果您在k交换后停止,则第一个k数字是k整个集合中随机的大小样本.