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

Question

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

注:已选k数字必须不同。

我正在考虑解决方案。我可以想到两种方法。让R是要返回的集合。

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

所以对于给定的 k我可以在 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]

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

1. value:前 k 个元素的数组，这将是结果选择。这被初始化为 {0..k-1}

2. rest:容量为 k 个条目的稀疏数据结构(例如哈希表)，包含数组的所有剩余条目，这些条目不是简单的自己的指数。最初是空的。

现在我们可以定义从值数组中交换元素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

对于 k≤n 的任意值，使用 O(k) 空间和时间。

三种算法攻略

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

对于较小的 k，随机选择的元素重复的概率微不足道，朴素哈希表无疑是最简单的解决方案。另一方面，如果 k 是 n 的重要部分，哈希表主要是浪费空间，因为大小为 n 足以记录已看到哪些值。对于非常大的 k，随着样本填满，拒绝算法将花费太多时间，并且洗牌所需的完整 vector 不会比用于保存样本的 vector 多多少空间样本。

因此，实用的解决方案可能是使用三个解决方案中占用较少空间和时间的任何一个:对于足够大的 k 值，n 位bitvector 小于具有 k 个条目的哈希表，但不会大到拒绝概率显着(例如，n/64≤k ≤n/4)，使用位 vector 。对于较小的 k 值，使用简单的哈希表算法，对于接近 n 的 k 值，在完整的 n 元素 vector (但限于 k 步)。

因为我们只在 k>cn 的情况下才选择 O(n) 策略常数 c，复合算法仍然是 O(k) 时间和空间，因为在该约束下，n 在 O(k )。