java算法:数组
数组是最基本的数据结构。在java和大多数编程语言中都被定义为简单类型。数组的使用是开发有效算法的基础。
数组是相同类型数据的固定集合,它是连续存储的,通过下标来访问数组元素。由于它是与计算机的内存系统直接通讯,可以看成是最基本的数据结构。
例一:埃拉托色尼筛,打印出小于给定N的所有素数。
- publicclassPrimes{
-
publicstaticvoidmain(String[]args){
-
intN=Integer.parseInt(args[0]);
-
boolean[]a=newboolean[N];
-
for(inti=2;i<N;i++){
-
a[i]=true;
- }
-
for(inti=2;i<N;i++){
-
if(a[i]!=false){
-
for(intj=i;j*i<N;j++){
-
a[i*j]=false;
- }
- }
- }
-
for(inti=2;i<N;i++){
-
if(i>N-100){
-
if(a[i]){
-
System.out.println(""+i);
- }
- }
- }
- }
- }
public class Primes {
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
boolean [] a = new boolean[N];
for(int i = 2; i < N ; i++){
a[i] = true;
}
for(int i = 2; i < N ; i++){
if(a[i] != false){
for(int j = i; j * i < N; j++){
a[i * j] = false;
}
}
}
for(int i = 2; i < N ; i++){
if(i > N - 100){
if(a [i]){
System.out.println(" " + i);
}
}
}
}
}
上述代码,计算一个布尔型的数组,如果i是素数,a[i]为true,否则,a[i]为false。首先,把数组中的所有元素置为true,然后把对应下标为非素数(是已知素数的倍数)的数组元素设为false。如果在所有较小素数的倍数都被设为false值后,a[i]的值仍为true,那么它肯定是一个素数。
对于其他对象而言,对数组的引用很有价值,因为它们可以把数组作为高级对象来有效地使用。
例二:健壮的数组分配
如果程序使用者敲入一个巨大的数作为命令行参数,它可能产生OutOfMemoryError异常错误,因此:
- boolean[]a;
-
try{
-
a=newboolean[N];
-
}catch(OutOfMemoryExceptione){
-
System.out.println("Outofmemory.");
- }
boolean [] a;
try{
a = new boolean[N];
}catch(OutOfMemoryException e){
System.out.println("Out of memory.");
}
数组不仅准确地反映在大多数计算机上访问内存数据的基本方法,而且在应用中获得了广泛的应用,如,数组直接对应着向量,是描述具有下标的对象列表的数学术语。
例三:掷硬币模拟
- publicclassCoinFlip{
-
staticbooleanheads(){
-
returnMath.random()<0.5;
- }
-
publicstaticvoidmain(String[]args){
-
inti,j,cnt=0;
-
intN=Integer.parseInt(args[0]);
-
intM=Integer.parseInt(args[1]);
-
int[]f=newint[N+1];
-
for(j=0;j<=N;j++){
-
f[j]=0;
- }
-
for(i=0;i<M;i++,f[cnt]++){
-
for(cnt=0,j=0;j<=N;j++){
-
if(heads()){
- cnt++;
- }
- }
- }
-
for(j=0;j<=N;j++){
-
if(f[j]==0){
-
System.out.print(".");
- }
-
for(i=0;i<f[j];i+=10){
-
System.out.print("*");
- }
-
System.out.println("");
- }
- }
- }
public class CoinFlip {
static boolean heads(){
return Math.random() < 0.5;
}
public static void main(String[] args) {
int i,j,cnt = 0;
int N = Integer.parseInt(args[0]);
int M = Integer.parseInt(args[1]);
int [] f = new int[N + 1];
for (j = 0; j <= N; j++) {
f[j]=0;
}
for (i = 0; i < M; i++, f[cnt]++) {
for(cnt = 0, j = 0; j <= N; j++){
if(heads()){
cnt++ ;
}
}
}
for(j = 0; j <= N; j++){
if(f[j] == 0){
System.out.print(".");
}
for(i = 0; i < f[j]; i+= 10){
System.out.print("*");
}
System.out.println("");
}
}
}
从某种意义上说,当我们使用一个计算过的值来访问大小为N的数组时,只用一个操作就可以把N种可能性都考虑进去,效率上有了很大的提高。
例四:最近点计算
- publicclassClosePoints{
-
publicstaticvoidmain(String[]args){
-
intcnt=0;
-
intN=Integer.parseInt(args[0]);
-
doubled=Double.parseDouble(args[1]);
-
Point[]a=newPoint[N];
-
for(inti=0;i<N;i++){
-
a[i]=newPoint();
- }
-
for(inti=0;i<N;i++){
-
for(intj=i+1;j<N;j++){
-
if(a[i].distance(a[j])<d){
- cnt++;
- }
- }
- }
-
System.out.println(cnt+"pairscloserthan"+d);
- }
- }
public class ClosePoints {
public static void main(String[] args) {
int cnt = 0;
int N = Integer.parseInt(args[0]);
double d = Double.parseDouble(args[1]);
Point [] a = new Point[N];
for(int i = 0; i < N; i++){
a[i] = new Point();
}
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
if(a[i].distance(a[j]) < d){
cnt++;
}
}
}
System.out.println(cnt + " pairs closer than " + d);
}
}
作为一个原型二次算法,它检查了N个数据项集合的所有数据对时,因此所花的时间与N平方成正比。
分享到:
相关推荐
计算机后端-Java-Java核心基础-第08章 数组 10. 算法:数组的复制.avi
在Java编程语言中,数组是一种基础且重要的数据结构...通过学习和实践上述知识点,对于Java算法题中的数组问题,你将能够游刃有余地进行解答。不断练习和深入理解数组的特性,可以提升你在算法设计和问题解决上的能力。
java 算法:包括数组,哈希表,队列,栈,链表(双端,单向,双向),二叉树(普通二叉树,哈夫曼树,二叉查找树,平衡二叉树,二叉线索树),图这些数据结构的实现以及多种排序算法和其他一些算法的实现(递归,二...
2. 初始化数组:声明数组的同时为其分配空间,如`int[] arr = new int[10];`,这创建了一个包含10个int元素的数组。 3. 访问数组元素:通过索引来访问数组元素,如`arr[0]`表示数组的第一个元素,`arr[9]`表示数组的...
本资源为Java数组练习题,共计15道题,涵盖了Java数组的基础知识点,包括数组的访问、数组的复制、数组的初始化、数组的下标、数组的长度、数组的存储、数组的下标越界、数组的元素类型、数组的默认值、数组的大小、...
JavaSE中的数组是一种重要的数据结构,它允许程序员存储和管理一组具有相同数据类型的元素。数组的概念可以类比为一个容器,...在实际编程中,数组常用于数据处理、排序算法等场景,是许多复杂数据结构和算法的基础。
40个Java算法与数组方面的源码实例集,这些代码都是比较简单,觉得很实用,有算法、数组、打印出杨辉三角形、求1 2! 3! ... 20!的和、递归方法实例、利用递归方法求阶乘之和、判断大小排序、球从100米高度自由落下,...
而"第五课:数组.ppt"则可能涵盖了数组的定义、创建、操作以及与之相关的高级话题,比如动态数组(ArrayList)、数组排序和搜索算法等。 学习这两个主题对于深入理解Java编程至关重要。数组帮助你有效地组织和处理...
实验可能包含编写代码示例,例如实现一个简单的数组排序算法(如冒泡排序或选择排序),或者创建一个二维数组模拟简单的矩阵运算。完成这样的实验有助于提升对数组操作的直观理解,增强编程能力。 在进行实验时,应...
2. **排序算法**:如冒泡排序、选择排序、插入排序等,理解它们的工作原理并在数组上实现。 3. **查找操作**:线性查找、二分查找等,学习查找特定元素的效率和方法。 4. **多维数组**:理解二维数组的概念,用于...
在 Java 中,数组是用于存储一组相同类型的元素的集合。下面是数组练习题的总结: 1. 排序算法 在数组练习题中,我们遇到了排序算法的应用。例如,在 Subject05 中,我们需要对 10 个整数进行按照从小到大的顺序...
在实际编程中,数组是解决许多问题的基础,比如实现动态规划、排序算法、查找算法等。对于数组的深入理解和灵活运用,是Java程序员必备的技能之一。 在Java中,数组是固定大小的,一旦创建,长度就不可改变。如果...
例如,排序算法中的快速排序或归并排序,就常常利用数组的引用传递来实现高效地交换和比较元素。 总之,理解Java中的数组引用传递是掌握面向对象编程的关键步骤之一。通过深入学习和实践,开发者能更好地控制程序的...
在算法竞赛中,为了避免“数组访问越界”的错误,数组一般会声明得稍微大一些。 - **定义位置**:较大的数组应尽量声明在主函数之外,否则可能会导致程序无法运行。 #### 二、数组的存储 数组在内存中的存储分为**...
在Java编程中,全排列是一个常见的问题,它涉及到算法和数据结构的知识。全排列是指从给定的字符数组中,按照一定的顺序生成所有可能的排列组合。这个问题通常使用回溯法来解决,因为它能够有效地避免重复的排列。...
在编程领域,数组是一种基础且重要的数据结构,尤其在Java编程语言中,它扮演着核心的角色。数组允许程序员存储和管理固定数量的同类型元素,这些元素可以通过索引来访问。本话题将深入探讨数组的概念、操作及在Java...
1. 添加元素到数组: 在Java中,数组一旦创建大小就固定不变,所以无法直接在数组末尾添加元素。但可以通过创建新的、更大容量的数组,并将旧数组的元素复制到新数组,然后添加新元素。或者使用ArrayList等动态数组...
理解数组的这些基本操作是学习Java的基础,也是进一步探索集合框架、算法和数据结构的前提。在实践中,我们还需要考虑数组的性能和内存占用,特别是在处理大数据量时。因此,学习如何有效地使用数组和优化相关算法,...