c++ - 在一个范围内生成不同的随机数

Question

我想在 1 和 N 之间生成 n 个不同的数字（当然是 n<=N）。N 可能非常大。如果 n 非常小，一种有效的方法是生成一个数字并将其与我们必须确保它是一个新数字的集合进行比较。它需要 O(n^2) 时间和 O(n) 内存。如果 n 很大，我们可以使用 Fisher-Yates shuffle 算法生成随机排列（在 n 步后停止）。这需要 O(n) 时间，但我们也必须使用 O(N) 内存。

这是问题。如果我们不知道 n 有多大，我们该怎么办？我希望算法只使用 O(n) 内存并在 O(n) 时间后停止。那可能吗？

Answer 1

您基本上可以对非常小的n执行相同的操作，但只是使该检查更有效。例如，检查您是否已经生成数字的简单方法是线性搜索先前生成的值的列表。对于未知的n，您可以对先前生成的值集进行排序，以便您可以使用更有效的搜索来识别重复项。使用朴素的方法，算法需要 O(n ² ) 时间，但通过以前的结果进行更智能的搜索可以将其减少到 O(n*log ₂ n)。