首页 > 代码库 > 生成N个不相等的随机数

生成N个不相等的随机数

          最近项目中需要生成N个不相等的随机数,实现的时候,赶工期,又有项目中N很小(0-100)直接谢了一个最直观的方法:

 public static List<Integer> randomSet(int num,int threshold){
        
        Random random = new Random();
        if(num > threshold) return null;
        
        Set<Integer> randomset = new HashSet<Integer>();
        while(randomset.size() < num)
            randomset.add(random.nextInt(threshold));
        List<Integer> result = new ArrayList<Integer>();
        result.addAll(randomset);
        
        return result ;
    }
       只要是根据HashSet 的来去重,到达不相等的随机数,但是当num比较大,或者num 比较接近threshold 的时候,这个时候平均期望比较大num*threshold*lognum 的复杂度

      其他类似的方法还有比如使用一个数组来标记某个数字是否已经标记到。复杂度同上


下面主要讲两个复杂度分别为num 和 threshold 的方法:
 

    方法 1 : 置乱(shuffle),代码如下:

 

      public static List<Integer> random_shuffle(int num,int thresold){
        
        Random rd = new Random();
        List<Integer> result = new ArrayList<Integer>(thresold);
        for(int i = 0 ;i < thresold ;i++)
            result.add(i+1);
        for(int i = thresold; i > 0;i--)
            swap(result,i-1,rd.nextInt(thresold));
        
        return result.subList(0, num);
    }
    
     将一个存有thresold 的数组,随机打乱顺序,然后返回前面num 个即可。也可以直接使用Collections.shuffle(list)方法。看源码可知,shuffle的算法也是如此。时间复杂度为threshold


方法 2  使用两个数组一个数组result 用来存结果 ,target用来存1到threshold 个数,每次从去一个小于threshold的随机数 r,然后从target 中取出放到result 中,同时,target 中交换r 和threshold-1的数,同时threshold--,这样保证这个数字以后再也不会取到。

代码如下:

 public static List<Integer> random_2(int num , int thresold){
        Random rd = new Random();
        List<Integer> target = new ArrayList<Integer>(thresold);
        for(int i = 0 ;i < thresold ;i++)
            target.add(i+1);
        List<Integer> result = new ArrayList<Integer>();
        
        for(int i = 0 ; i < num ;i++){
            int  r = rd.nextInt(thresold);
            result.add(target.get(r));
            swap(target, r, thresold-1);
            thresold--;
        }
        
        return result;
        
    }