algorithm - 从一组中获取 X 个唯一数字

Question

我认为获取唯一随机数的最优雅方法是什么？

目前我需要随机唯一数，我通过使用 while 循环检查它是否不是唯一的，看看我之前是否使用过随机数。

所以它看起来像:

int n = getRandomNumber % [Array Size];

for each ( Previously used n in list)
    Check if I've used n before, if I have...try again.

解决这个线性O(n/2)问题的方法有很多，我只是想知道有没有一种优雅的方法来解决它。试着回想一下 MATH115 离散数学，并记住老讲师是否涵盖了与看似微不足道的问题有关的任何内容。

我现在无法思考，所以也许一旦我摄入了一些咖啡因，我的大脑就会用咖啡引起的高智商来支持它。

Answer 1

如果您想要从集合 {1, ..., n} 中不放回地抽取 k 个随机整数(以获得唯一数字)，您需要的是 [n] 的随机排列中的前 k 个元素。生成这种随机排列的最优雅的方法是使用 Knuth 洗牌。看这里:http://en.wikipedia.org/wiki/Knuth_shuffle