在一个范围内随机选择 k 个不同的数字

Question

我需要 select k 范围内随机的元素 0 to n-1。 n 可以达到 10^9。 k 的范围可以是 1 to n-1。我可以在 O(n) 时间内完成此操作，只需将包含值 0 to n-1 的数组改组并从中选择第一个 k 元素。但是当 k 很小时，这种方法在时间和内存上都是低效的。这个问题有O(k)的解决方案吗？

注意：Selected k 数字必须不同。

我在想办法。我可以想到两种方法。让R是要返回的集合。

Select范围内的一个随机值并将其添加到R。继续这样做，直到 |R| = k。这个过程需要 sum(n/i) for n+1-k <= i <= n 时间和 O(k) space.
在数组中插入 0 到 n-1，打乱它，从中取出前 k 个元素。这个过程需要 O(n+k) 时间和 space.

因此，对于给定的 k，我可以 select 在 O(k) 时间内使用更可取的方法。

Answer 1

改进的 Fisher-Yates 算法

可以改进混洗解决方案，因为您只需混洗数组的前 k 个元素。但这仍然是 O(n) 因为天真的洗牌实现需要一个大小为 n 的数组，需要将其初始化为 n 值从 0 到 n-1.

Initialize value[n] to {0..n-1}
For i from 0 to k-1:
  swap(value[i], value[random_in_range(i, n)])
Result is value[0..k-1]

为了改进这一点，我们可以使用一种虚拟数组，由两部分组成：

value：前 k 个元素的数组，这将是结果选择。这被初始化为 {0..k-1}
rest：容量为k[=83=的稀疏数据结构（例如散列table） ] 条目，包含数组的所有剩余条目，这些条目不仅仅是它们自己的索引。初始为空。

现在我们可以定义从 value 交换元素 i 和 j 的函数数组（注：i<k，如上算法保证）：

# To swap elements i and j If j < k: # Both elements to be swapped are in the selection tmp = value[i]; value[i] = value[j]; value[j] = tmp Else If j in rest: # Element j has been swapped before tmp = value[i]; value[i] = rest[j]; rest[j] = tmp Else: # The value at j is still j, we now add it to the virtual array rest[j] = value[i]; value[i] = j

即使用O(k)space和时间，对于k≤的任意值n.

三种算法攻略

使用 O(k) 内存的更简单的解决方案是只保留所有选定值的散列table，并生成值直到散列table 包含 k 个值，拒绝重复。

对于小 k，随机选择的元素重复的概率微不足道，朴素的哈希table当然是最简单的解决方案。另一方面，如果 k 是 n 的重要部分，则散列 table 大部分被浪费了 space，因为大小为 n 的简单位向量就足以记录已看到哪些值。并且对于非常大的 k，拒绝算法会花费太多时间，因为样本会填满，而洗牌所需的全向量并不比向量多 space用来盛放样品。

因此，实用的解决方案可能是使用三种解决方案中使用较少 space 和时间的任何一种：对于 k 的值足够大，以至于 n 位位向量小于具有 k 条目的散列 table，但不会大到拒绝概率显着（例如， n/64≤k≤n/4), 使用位向量。对于k较小的值，使用简单的hashtable算法，对于k的值接近n ，在完整的 n 元素向量上使用 Fisher-Yates 洗牌（但限于 k 步骤）。

因为我们仅在 k>c[=124= 的情况下才选择 O(n) 策略]n对于某个常数c，复合算法仍然是O(k)时间和space 因为有了这个约束，n 在 O(k).
中

在一个范围内随机选择 k 个不同的数字

Randomly selecting k different numbers in a range

java

sorting

random

algorithm

random-sample

改进的 Fisher-Yates 算法

三种算法攻略