美文网首页
不重复随机

不重复随机

作者: 已经是咸鱼的小涛orz | 来源:发表于2017-08-22 11:15 被阅读0次

方案一、无序不重复数列

通过无序数列代替随机数,如:[7, 2, 8, 4, 9, 0]
现在我们模拟一个随机数范围在 [0,4] 的序列
①首先,初始化一个顺序数组,数组大小等于所需最大随机数 #Seq:【0,1,2,3,4】
②以 5 为基数随机一个下标 # i = 3
③取i=3的值 3 ,得数组 out:【3】
④在Seq序列中移除seq[3],得数组Seq:【0,1,2,4】
⑤循环②③④ 得最终序列out:【3, 4, 0, 1, 2】
Tip:
当数组中remove一个值时,该下标之后的所有值都往前挪动一位,因此,当数组较大时,耗时会很大,严重印象效率
优化
在④中,不再直接remove seq[i],改为将seq[i]与seq[end]互换,即此时序列为 Seq:【0,1,2,4,3】;
而后,在②中,不再以 5 为基数随机,改为length-1 = 4,即默认移除了最后一位seq[end] ,Seq:【0,1,2,4】
这样就只需要做一次互换处理,不需要对 i 之后的所有值全体向前挪动一位

最终代码

/**
 * 无序不重复数列
 * @param maxNum 数值范围
 * @param total  数列大小
 * @return  随机序列
 */
private int[] getNoDuplicatesRandom(int maxNum, int total) {
    int[] sequence = new int[maxNum];
    int[] output = new int[total];
    for (int i = 0; i < maxNum; ++ i) {
        sequence[i] = i;
    }
    int position;
    Random random = new Random();
    for (int i = 0; i < total; ++ i) {
//      System.out.println("sequence: " + Arrays.toString(sequence));
        position = random.nextInt(maxNum)%maxNum;
//      System.out.println("position: " + position);
        output[i] = sequence[position];
//      System.out.println("output: " + Arrays.toString(output));
        sequence[position] = sequence[--maxNum];
    }
    return output;
}

以下为对[0.10)取最多6位随机数的结果

sequence: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
position: 7
output: [7, 0, 0, 0, 0, 0]
sequence: [0, 1, 2, 3, 4, 5, 6, 9, 8, 9]
position: 2
output: [7, 2, 0, 0, 0, 0]
sequence: [0, 1, 8, 3, 4, 5, 6, 9, 8, 9]
position: 2
output: [7, 2, 8, 0, 0, 0]
sequence: [0, 1, 9, 3, 4, 5, 6, 9, 8, 9]
position: 4
output: [7, 2, 8, 4, 0, 0]
sequence: [0, 1, 9, 3, 6, 5, 6, 9, 8, 9]
position: 2
output: [7, 2, 8, 4, 9, 0]
sequence: [0, 1, 5, 3, 6, 5, 6, 9, 8, 9]
position: 0
output: [7, 2, 8, 4, 9, 0]

相关文章

网友评论

      本文标题:不重复随机

      本文链接:https://www.haomeiwen.com/subject/wvnkdxtx.html