生成不重复的随机整数算法分析

?

算法一：????????用一个List保存所有候选的整数，依次 生成一个随机索引（该索引的范围需要递减），返回该元素，并移除该索引对应的元素值。（缺点：该算法经测试大概1M 的整数范围需要用到约16M 的内存空间，所以对于 大数据范围，多线程且每个线程分别独立生成不重复的随机整数 的情况下不太适用。 优点：该算法的可读性最强；而且因为会移除返回的元素，所以占用的内存会动态逐渐减少。）所以此处没有给出代码示例。?算法二：????????用一个数组保存所有候选的整数，依次 生成一个随机索引（该索引的范围需要递减），返回该元素，并 将末尾元素赋值到索引位置 且将原末尾元素位置前一个元素作为新的末尾元素。（缺点：可读性比上面的算法弱一点；占用内存一直不变。 优点：该算法经测试大概 1M 的整数范围需要用到约 4M 的内存空间（因为一个int数据占用4个Byte），比上面的算法好一点；时间复杂度比较低。）代码示例：

package com.kangfuqiang.util;import org.slf4j.Logger;import org.slf4j.LoggerFactory;/** * <pre>  * Title:不重复的随机整数类 * Description: 用于依次获取 [MIN,MAX] 范围内的不重复随机整数； * 使用说明：需要new一个该类的实例（传入min和max参数），然后 使用该实例 依次获得不重复的随机整数； *  * ps：1M 的整数范围时，该实例占用的相关内存约为 4M 。 *  * </pre> */public class NoRepeatRandomInt {    private static Logger log = LoggerFactory.getLogger(NoRepeatRandomInt.class);        /** 最小值（包含） */    public final int MIN;    /** 最大值（包含） */    public final int MAX;            /** 计数器，记录已经领取不重复的随机整数的次数 */    private int counter = 0;        /** 保存 [MIN,MAX] 范围内的所有整数*/    private int[] numArr ;           /**     * @param min     * @param max     * @exception IllegalArgumentException 如果 min > max，则抛出该异常     */    public NoRepeatRandomInt(int min, int max) {        if(min>max){            String str = String.format("构造器参数错误，最小值不能大于最大值！min:%s,max:%s", min, max);            log.error(str);            throw new IllegalArgumentException( str );        }        this.MIN = min;        this.MAX = max;        numArr = new int[this.getOriginalCnt()];        for(int i=0; i<numArr.length; i++){            numArr[i] = i + this.MIN;        }    }        /**     * 领取 下一个不重复的随机整数     * @return     * @exception RuntimeException 如果 领取次数 超过 总个数范围，将抛出运行时异常     */    public int next(){        if(this.getRemainCnt()<=0){            String str = String.format("领取次数 超过 总个数范围（%d个）!", this.getOriginalCnt());            log.error(str);            throw new RuntimeException(str);        }        int idx = (int)(Math.random() * this.getRemainCnt());        int ret = numArr[idx];        numArr[idx] = numArr[this.getRemainCnt()-1];        numArr[this.getRemainCnt()-1] = ret;         this.counter++;        return ret;    }        /** 获得原始个数 */    private int getOriginalCnt(){        return this.MAX - this.MIN + 1;    }        /** 获得剩余个数 */    private int getRemainCnt(){        return this.MAX - this.MIN + 1 - counter;    }}

???算法三：????????使用Set集合来保证或保存不重复的随机整数。 这种算法适合 （返回数目/ 范围数目）的值非常小 的情况，其他情况还是使用上面的两种算法比较好。?PS：网上还有一些其他的算法，但是大多时间复杂度比较高，空间复杂度也没有明显的好处。1、遍历 已返回的随机数 的集合，以保证不重复随机整数。2、初始化List后，随机排序一下（shuffle），然后依次返回。3、初始化数组后，数组随机调换位置，然后依次返回。?欢迎大家交流、指点、评论与回复