如何在 C++ 中从（可能很大）范围生成一组随机数字？

Question

我正在尝试从给定范围生成一组

n

数字，以便该范围内的所有数字都有平等的机会出现在最终集合中。

我发现的一种方法是拥有一个包含范围内所有数字的数组，然后对其进行洗牌，然后取出数组中的第一个

n

值。如果范围变大，这在空间上是不可行的。

最好的方法是什么？

Answer 1

我认为它与 C++ 没有任何关系（除了使用像

std::vector

和

std::uniform_int_distribution

这样明显的东西）。

如果您想让算法在有限时间内工作，您可以执行以下操作：

从空数组开始，步骤

i

范围为

[0, n)

:

• 从原始范围的开头开始到原始范围的末尾结束的范围生成一个值减去

  i

  。
• 从数组的开头开始，枚举其中的值。如果数组中的值小于或等于您刚刚生成的值，请将生成的值加一并继续枚举数组中的值。
• 如果您达到的值大于您生成的值（加上所有添加的值），请将新值插入到数组中的所有值之前。如果到达数组末尾，请将新值插入到数组末尾。这将使数组保持升序排序。

最后随机打乱数组。

这会给你

O(n²)

时间复杂度。

通过使用平衡二叉树而不是数组，您可以达到

O(n*log(n))

时间复杂度，但如果您从头开始编写解决方案，那么所获得的收益可能不值得您在调试此类解决方案上花费的精力。