java算法：数组

java算法：数组

数组是最基本的数据结构。在java和大多数编程语言中都被定义为简单类型。数组的使用是开发有效算法的基础。

数组是相同类型数据的固定集合，它是连续存储的，通过下标来访问数组元素。由于它是与计算机的内存系统直接通讯，可以看成是最基本的数据结构。

例一：埃拉托色尼筛，打印出小于给定N的所有素数。

Java代码 复制代码
  1. public class Primes {   
  2.     public static void main(String[] args) {   
  3.         int N = Integer.parseInt(args[0]);   
  4.         boolean [] a = new boolean[N];   
  5.         for(int i = 2; i < N ; i++){   
  6.             a[i] = true;   
  7.         }   
  8.         for(int i = 2; i < N ; i++){   
  9.             if(a[i] != false){   
  10.                 for(int j = i; j * i < N; j++){   
  11.                     a[i * j] = false;   
  12.                 }   
  13.             }   
  14.         }   
  15.         for(int i = 2; i < N ; i++){   
  16.             if(i > N - 100){   
  17.                 if(a [i]){   
  18.                     System.out.println(" " + i);   
  19.                 }   
  20.             }   
  21.         }   
  22.     }   
  23.   
  24. }  

上述代码，计算一个布尔型的数组，如果i是素数，a[i]为true，否则，a[i]为false。首先，把数组中的所有元素置为true，然后把对应下标为非素数（是已知素数的倍数）的数组元素设为false。如果在所有较小素数的倍数都被设为false值后，a[i]的值仍为true，那么它肯定是一个素数。

对于其他对象而言，对数组的引用很有价值，因为它们可以把数组作为高级对象来有效地使用。

例二：健壮的数组分配

如果程序使用者敲入一个巨大的数作为命令行参数，它可能产生OutOfMemoryError异常错误，因此：

Java代码 复制代码
  1. boolean [] a;   
  2. try{   
  3.     a = new boolean[N];   
  4. }catch(OutOfMemoryException e){   
  5.     System.out.println("Out of memory.");   
  6. }  

数组不仅准确地反映在大多数计算机上访问内存数据的基本方法，而且在应用中获得了广泛的应用，如，数组直接对应着向量，是描述具有下标的对象列表的数学术语。

例三：掷硬币模拟

Java代码 复制代码
  1. public class CoinFlip {   
  2.     static boolean heads(){   
  3.         return Math.random() < 0.5;   
  4.     }   
  5.     public static void main(String[] args) {   
  6.         int i,j,cnt = 0;   
  7.         int N = Integer.parseInt(args[0]);   
  8.         int M = Integer.parseInt(args[1]);   
  9.         int  [] f = new int[N + 1];   
  10.         for (j = 0; j <= N; j++) {   
  11.             f[j]=0;   
  12.         }   
  13.         for (i = 0; i < M; i++, f[cnt]++) {   
  14.             for(cnt = 0, j = 0; j <= N; j++){   
  15.                 if(heads()){   
  16.                     cnt++ ;   
  17.                 }   
  18.             }   
  19.         }   
  20.         for(j = 0; j <= N; j++){   
  21.             if(f[j] == 0){   
  22.                 System.out.print(".");   
  23.             }   
  24.             for(i = 0; i < f[j]; i+= 10){   
  25.                 System.out.print("*");   
  26.             }   
  27.             System.out.println("");   
  28.         }   
  29.     }   
  30. }  

 从某种意义上说，当我们使用一个计算过的值来访问大小为N的数组时，只用一个操作就可以把N种可能性都考虑进去，效率上有了很大的提高。

例四：最近点计算

Java代码 复制代码
  1. public class ClosePoints {   
  2.   
  3.     public static void main(String[] args) {   
  4.          int cnt = 0;   
  5.          int N = Integer.parseInt(args[0]);   
  6.          double d = Double.parseDouble(args[1]);   
  7.          Point [] a = new Point[N];   
  8.          for(int i = 0; i < N; i++){   
  9.              a[i] = new Point();   
  10.          }   
  11.          for(int i = 0; i < N; i++){   
  12.              for(int j = i + 1; j < N; j++){   
  13.                  if(a[i].distance(a[j]) < d){   
  14.                      cnt++;   
  15.                  }   
  16.              }   
  17.          }   
  18.          System.out.println(cnt + " pairs closer than " + d);   
  19.     }   
  20.   
  21. }  

作为一个原型二次算法，它检查了N个数据项集合的所有数据对时，因此所花的时间与N平方成正比。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wuyida/p/6301157.html