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 算法:包括数组,哈希表,队列,栈,链表(双端,单向,双向),二叉树(普通二叉树,哈夫曼树,二叉查找树,平衡二叉树,二叉线索树),图这些数据结构的实现以及多种排序算法和其他一些算法的实现(递归,二...
40个Java算法与数组方面的源码实例集,这些代码都是比较简单,觉得很实用,有算法、数组、打印出杨辉三角形、求1 2! 3! ... 20!的和、递归方法实例、利用递归方法求阶乘之和、判断大小排序、球从100米高度自由落下,...
主要介绍了Java实现字符数组全排列的方法,涉及Java针对字符数组的遍历及排序算法的实现技巧,需要的朋友可以参考下
初级练习
java函数学习之查找函数使用,是在学习java过程中的一个小例子
java 二个数组的交集,算法 java 二个数组的交集,算法
简介:在这个Java编程示例中,我们展示了如何有效地查找整数数组中的最大值。通过一个名为 `findMax` 的自定义方法,...这个小程序可以作为学习Java算法和数据结构的起点,让您更好地理解数组遍历和值比较的基本概念。
先声明一个数组,这个数组中可能会存在重复的元素,而且顺序也是杂乱的,要求将这个数组中的重复元素排除掉并将新得到的数组进行递增排序
算法设计与分析(王晓东版)2-11题:将数组的子数组a[0:k]和a[k+1:n-1]进行换位,要求最坏情况下时间复杂度为O(n)
//数组的第一个数设为最小值 for(i=1;i;i++) //因为min=[0],所以i从1开始 { if(a[i]) //如果有比min小的数,就将这个数赋值给min { min=a[i]; minindex=i;//记录下标 } } minindex++; ...
java可运行排序算法:①插入排序、②冒泡排序、③选择排序、④学生学号按照成绩高低排序的一个简单...在java工程项目的源文件src中建立Array包,可运行这四个.java文件,便于对java中的排序算法及数组结构进一步了解。
例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和...
本资料为博客中对应的Leecode中初级算法的数组题代码,编程语言为java
这份资源提供了Java数组排序的全面指南。该文档涵盖了数组排序的基本概念,包括如何实现各种排序算法,如冒泡排序、选择排序、插入排序、归并排序和快速排序。此外,文档还为每个排序算法提供了详细的代码示例和实现...
[Java算法练习]-数组交换.java
涵盖:数组、链表、栈、堆、二叉树、BST树等数据结构,算法有搜索、排序、去重、找出现次数最多等问题。 使用Java8来实现 2. 两数相加 迭代法 因为从链表往下个节点变换时,依次是个位、十位、百位 从链表头向下依次...
[Java算法练习]-数组逆序输出.java