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

Question

我需要k在范围内随机选择元素0 to n-1.n最高可达10 ^ 9.并且k可以从1 to n-1.我可以在O(n)时间内通过对包含值的数组进行混洗0 to n-1并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算法

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

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

使用O(ķ)的空间和时间,对于任意值ķ ≤ Ñ.

三种算法策略

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

对于小k,随机选择的元素是重复的概率是无关紧要的,并且天真的哈希表肯定是最简单的解决方案.另一方面,如果k是n的重要部分,则散列表主要是浪费的空间,因为大小为n的简单位向量足以记录已经看到的值.对于非常大的k,拒绝算法将在样本填满时花费太多时间,并且shuffle所需的完整向量不会比用于保持样本的向量多得多.

因此,实用的解决方案可能是使用三种解决方案中使用较少空间和时间的任何一种:对于足够大的k值,n位比特向量小于具有k个条目但不大于概率的哈希表的排斥反应是显著(比方说,ñ /64≤ ķ ≤ ñ/4),可以使用位向量.对于较小的k值,使用简单的散列表算法,对于接近n的k值,在完整的n元素向量上使用Fisher-Yates shuffle (但限于k步).

由于我们仅在某些常数c的k > c n的情况下选择O(n)策略,因此复合算法仍然是O(k)时间和空间,因为在该约束下,n在O(k)中.