从集合中获取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 shuffle.见这里:http://en.wikipedia.org/wiki/Knuth_shuffle