一尘不染

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

algorithm

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

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

阅读 261

收藏
2020-07-28

共1个答案

一尘不染

您可以使用通过交换实现的部分Fisher-
Yates随机播放
。该算法的一个不错的功能是,如果您在k交换后停止,则第一个k数字是k来自完整集合的随机大小样本。

2020-07-28