等概率不重复的生成随机数应该是在平时开发中常见的，也是面试中常问的基础之一。有多种实现方式，有人人都可以想到的，也有不容易想到的巧妙算法，那么当有人问你哪个实现方式更好的时候你该怎么回答呢？回答巧妙的算法比普通算法好？答案显而易见，首先要搞清楚应用场景和要解决的问题。这样才能判断一个算法或者方案的合适与否。

　　接下来明确问题、提出多个解决方法，最后对比每个方法的优劣与使用场景。

　　要求：

　　可能有些具体的场景和问题需求都不一样，可以统一：在一定范围内等概率不重复的生成有限个随机数。具体的可以定义为，在[m,n]之间等概率的生成k个不相同的随机数。

　  设计与实现：

　　1.排重

　　一个最简单的想法就是先生成再排重，直到生成k个随机数为止。把所有用到排重的算法都可以归为一类，包括利用Map、Set、BitMap、数组下标去重的都算。因为本质上是一样的，可能在排重的时候有些优化。

public List
     
       random1(int m, int n, int k) {        if (k < 1 || k > n-m+1) {            System.out.println("Params is illegal.");        }                Random random = new Random();        List
      
        ret = new ArrayList
       
        ();        while (ret.size() < k) {            Integer rand = random.nextInt(n-m+1)+m; //生成[m,n]之间的随机数            if (!ret.contains(rand)) {                ret.add(rand);            }        }        return ret;    }
       
      
     

 

　　排重的一种改进算法，数组下标去重：

//优化去重    public List
     
       random2(int m, int n, int k) {        if (k < 1 || k > n-m+1) {            System.out.println("Params is illegal.");        }        Random random = new Random();        List
      
        ret = new ArrayList
       
        ();        int[] flag = new int[n-m+1];        Arrays.fill(flag, 0);        while (ret.size() < k) {            Integer rand = random.nextInt(n-m+1)+m; //生成[m,n]之间的随机数            if (flag[rand-m] == 0) {                ret.add(rand);                flag[rand-m] = 1;            }        }        return ret;    }
       
      
     

　　2.移动

　　把[m,n]之间的数放到一个数组中，随机生成一个范围内的下标把选中的下标的值移动到最后一个，其余的向前移动。之后生成[m,n-1]范围内的下标，依次类推，直到生成了k个随机数。

 

//移动    public List
     
       random3(int m, int n, int k) {        if (k < 1 || k > n-m+1) {            System.out.println("Params is illegal.");        }        Random random = new Random();        List
      
        ret = new ArrayList
       
        ();        int[] arr = new int[n-m+1];        int j = m;        for (int i=0; i
        
          0 && n-m+1-cur < k) {            int randIndex = random.nextInt(cur);            int randValue = arr[randIndex];            ret.add(randValue);            for (int i=randIndex+1; i
        
       
      
     

 

　　3.交换

 

　　这种思路和上个移动的想法差不多，但不是再移动数组，而是交换。简单来说就是选择随机生成数组下标之后和下标为i-1的交换。直到每个元素都被交换过一遍。然后可以截取这个数组的k个元素。

//交换    public List
     
       random4(int m, int n, int k) {        if (k < 1 || k > n-m+1) {            System.out.println("Params is illegal.");        }        Random random = new Random();        List
      
        ret = new ArrayList
       
        ();        int[] arr = new int[n-m+1];        int j = m;        for (int i=0; i
        
         =0; i--) {            int randIndex = random.nextInt(n-m+1);            int t = arr[randIndex];            arr[randIndex] = arr[i];            arr[i] = t;        }        for (int i=0; i
        
       
      
     

 

　　熟悉Java的同学都知道JDK中集合工具里有个shuffle洗牌方法，其核心思想就是随机交换。JDK-shuffle源码：

public static void shuffle(List
      list, Random rnd) {        int size = list.size();        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {            for (int i=size; i>1; i--)                swap(list, i-1, rnd.nextInt(i));        } else {            Object arr[] = list.toArray();            // Shuffle array            for (int i=size; i>1; i--)                swap(arr, i-1, rnd.nextInt(i));            // Dump array back into list            // instead of using a raw type here, it's possible to capture            // the wildcard but it will require a call to a supplementary            // private method            ListIterator it = list.listIterator();            for (int i=0; i

　　比较：

　　首先把问题分成几种情况，规定以下指标：数据范围大小amount=n-m+1，数据量大小k=[big, small]，big代表接近amount，small代表更接近0。

　　1.amount较小的情况下，其实差别不大，从时空复杂度上没有区分度。

　　2.amount较大的情况下，k=small。排重要好于交换和移动。因为要选择出来的随机数数量要比范围小得多，这样一来如果要交换整个范围内的序列就会在效率上打折扣。因为在大范围选取个别随机数碰撞的概率较小所以排重工作就少了，这种情况下排重算法更好。

　　3.amount较大的情况下，k=big。交换要好于移动和排重。因为在大范围内生成大量的随机数那么碰撞的几率就会变大，而且越往后越大，试想一下，如果要在100W个数中随机出99W个随机数，到生成第99W个随机数的时候碰撞率已经高达99%了。这是绝对忍受不了的。而反观交换算法，因为k比较接近amount所以交换整个序列不会浪费太多交换次数。遍历序列就能把整个序列等概率的shuffle一遍，然后截取k个即可。这种方法显然要高效许多。

 

　　更好的算法有待补充。。。