随机序列生成算法---生成前N个整数的一组随机序列

问题描述:

给定输入N,生成从1开始的:1,2,3,4,......N 一组随机序列,序列中的数不能重复出现。

比如:N=5,合法的随机序列为{4,3,1,5,2} 、{3,1,4,2,5}……非法的序列有{5,4,1,2,1}

来源:《数据结构与算法分析-MAW著  第二章习题2.8》

 

思路1:

对于数据a[N]而言,当随机生成第i个数a[i]时,确保a[i]在 a[0]至a[i-1]中没有出现过,就把该数放入a[i],继续生成下一个数a[i+1]

算法复杂度为O(N^2logN)---每生成一个a[i],需要扫描a[0]...a[i-1]。

随机序列生成算法---生成前N个整数的一组随机序列
public static int[] algorithm1(int N) {  
            int []a = new int[N];  
            for (int i = 0; i < a.length; ++i) {    
                while (true) {  
                    a[i] = randInt(1, N); //生成[1,N]之间的一个随机数         
int j = 0;
for (; j < i; ++j) { if (a[i] == a[j]) { break;//如果这个随机数已经在前面出现过了,break,下一轮继续生成另一个随机数,直至a[i]与前面所有的数不同 } } //end for if(j == i)   break;//本次生成的a[i]在前面没有出现过, break while, i++,下一轮生成a[i+1] }//end while } return a; }
随机序列生成算法---生成前N个整数的一组随机序列

 

思路2:

先以1,2,3,.....N 初始化数组a[N],然后随机选择一个数组下标,交换这两个下标处的值。

算法复杂度为O(N)

随机序列生成算法---生成前N个整数的一组随机序列
public static int[] algorithm3(int N){
          int[] a = new int[N];
          for(int i = 1; i <= N; i++)
              a[i-1] = i;
          for(int i = 1; i < N; i++)
              swapReference(a, i, randInt(0, i));
          return a;
      }
      
      private static void swapReference(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
      }
随机序列生成算法---生成前N个整数的一组随机序列

 

JAVA中采用java.util.Random类的nextInt(int n)方法可生成一个[0,n)的随机数。---包括0不包括n

要生成范围[i,j]内的一个随机数,方法如下:

①nextInt(j-i+1)----生成[0, j-i+1)之间的随机数

②nextInt(j-i+1)+i  生成 [i, j+1)之间的随机数,即为[i,j]内的一个随机数了。

 

性能比较:当N=1w时,algorithm1用时42ms,algorithm3用时2ms

当N=10w时,algorithm1用时2806ms,algorithm3用时12ms

整个程序代码如下:

随机序列生成算法---生成前N个整数的一组随机序列
import java.util.Random;

public class C2_2_8 {
    
    private static Random rand = new Random(47);
    //生成一个[i,j]之间的随机数
    public static int randInt(int i, int j){
        return rand.nextInt(j-i+1) + i;
    }
    
      public static int[] algorithm1(int N) {  
            int []a = new int[N];  
            for (int i = 0; i < a.length; ++i) {    
                while (true) {  
                    a[i] = randInt(1, N); //生成[1,N]之间的一个随机数         
                    for (int j = 0; j < i; ++j) {    
                        if (a[i] == a[j]) {  
                            break;//如果这个随机数已经在前面出现过了,break,下一轮继续生成另一个随机数,直至a[i]与前面所有的数不同  
                        }  
                    } //end for
                    
                    
                    break;//本次生成的a[i]在前面没有出现过, break while, i++,下一轮生成a[i+1]
                }//end while 
            }
            return a;  
        }  
    
      
      public static int[] algorithm3(int N){
          int[] a = new int[N];
          for(int i = 1; i <= N; i++)
              a[i-1] = i;
          for(int i = 1; i < N; i++)
              swapReference(a, i, randInt(0, i));
          return a;
      }

      //生成一个即有正数又有负数的随机数组
      public static int[] randomArr(int N){
          int [] a = new int[N];
          for(int i = 1; i <= N/2; i++)
              a[i-1] = i;
          for(int j = N; j > N/2; j--)
              a[j-1] = -j;
          for(int i = 1; i < N; i++)
              swapReference(a, i, randInt(0, i));
          return a;
      }
private static void swapReference(int[] a, int i, int j){ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } public static void main(String[] args) { long start3 = System.currentTimeMillis(); algorithm3(100000); System.out.println(System.currentTimeMillis() - start3); long start = System.currentTimeMillis(); algorithm1(100000); long time = System.currentTimeMillis() - start; System.out.println(time); } }
随机序列生成算法---生成前N个整数的一组随机序列
上一篇:EclipseIDE常用快捷键


下一篇:HTTP状态码大全