产生一组不重复随机数的高效算法

时间:2021-01-30 09:50:15

需要从 0 到 n 之间选 k 个不重复的数组成一个序列。

最早我想的是用一个辅助数组记录之前已经产生的随机数,如果当前产生的随机数已经出现过就再重新随机。

显然这样的实现效率是很低的,设想从10000个数中随机产生10000个数的序列,当前面9999个数已经确定了时,最后一个数被随机到的概率是 0.0001,也就是说大概需要调用随机函数10000次才会产生。类似的,第9999个数被随机到的概率是0.0002……
…..

那么,高效的算法来了

先上代码:
需求:从 0 到 n 之间选 k 个不重复的数组成一个序列。

假设 n =4;k=4;(k<=n);

int n = 4;
int k = 4;
//生成0~n之间的数组
int[] x = new int[n];
for (int i = 0; i < n; i++) {
    x[i] = i;
}
//开始随机 k 个不重复数出来
for (int i = 0; i < k; i++) {
    Random random = new Random();
   // t : i 至 n 的随机数
   // 目的:不再随机出已置换出去 的数 的下标
   int t = random.nextInt(n - i) + i;
   // 交换x[i],x[t]的值
   int temp = x[i];
   x[i] = x[t];
   x[t] = temp;
   //此时输出x[i]的值,就是第i 个随机出的数。
   System.out.println("随机数== " + x[i]);
}

文采不好,直接进入灵魂画师环节。。。。

产生一组不重复随机数的高效算法

再来一段小描述:

首先,x数组里把0到n-1的所有数都存储了,而最后输出的都是x数组里的值,所以满足输出的数是k个0到n-1的数。

然后,我们对于第 i 次随机,产生一个 i 到 n-1 的下标 t ,并把x[t] 和x[i]交换,将其输出,这样每次产生的数都是之前没有出现过的数,因为之前出现过的数都在x[0] 到 x[i-1]里呢!这样就保证了输出数据的不重复性。


可以了吧!

关注微信公众号,长期干货分享
产生一组不重复随机数的高效算法