文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

揭开数组的真面目

2024-12-11 17:00

关注

数组做为一种基础的数据存储结构,应用十分广泛。数组是用连续的内存空间来存储固定长度的、相同数据类型的一种数据结构。数据结构是跟语言无关的,这里,使用java来进行数组的相关操作。数组的索引是从0开始的。

 

一 数组初始化

创建数据有两种方式,一种是先申请一个固定长度的数据,然后再给数组赋值,另一种是直接赋值。

第一种:

  1. 数据类型[] 数组名称 = new 数据类型[长度]; 

这里的[]标识这申明了一个数组,这个[]除了可以放在数据类型后面,也可以放在数组名词后面,效果一样。假如我申明一个长度为2的long类型的数组,并赋值:

  1. long[] arr = new long[2]; 
  2. arr[0] = 1; 
  3. arr[1] = 2; 

第二种:

  1. 数据类型[] 数组名称 = {元素1,元素2, ...}; 

这样在数组初始化的时候直接给数组赋值,数组的长度由元素的个数决定。

二 自定义类封装数组实现数据操作

  1. public class MyArray { 
  2.  
  3.     // 自定义数组 
  4.     private long[] arr; 
  5.     // 有效数据长度 
  6.     private int element; 
  7.  
  8.     public MyArray(){ 
  9.         arr = new long[9]; 
  10.     } 
  11.  
  12.     public MyArray(int maxsize){ 
  13.         arr = new long[maxsize]; 
  14.     } 
  15.      
  16.     public void display(){ 
  17.         System.out.print("["); 
  18.         for (int i = 0; i < element; i++) { 
  19.             System.out.print(arr[i]+" "); 
  20.         } 
  21.         System.out.print("]"); 
  22.     } 

2.1 添加元素

数组是用连续的内存空间来存储数据的,则每次添加的时候会往当前数组的最后一个元素上添加元素,一次就可以加上元素,所以它的复杂度为O(1),假如定义一个长度为9数组,数组中已经有两个元素,则添加第三个元素如下:

  1. public void add(long value){ 
  2.     arr[element] = value; 
  3.     element++; 

2.2 根据值查询元素位置

这种查找方式也叫做线性查找,就是根据传入的值循环去遍历元素,来获取对应的位置,理论上平均查询一个元素需要花费N/2次,所以它的复杂度为O(N)。

  1. public int find(long value){ 
  2.     int i; 
  3.     for (i = 0; i < element; i++) { 
  4.         if(value == arr[i]){ 
  5.             break; 
  6.         } 
  7.     } 
  8.     if(i == element){ 
  9.         return -1; 
  10.     }else { 
  11.         return i; 
  12.     } 

2.3 根据索引查询元素

根据索引来查找元素,也就是获取对应位置的元素,其复杂度为O(1)。

  1. public long get(int index){ 
  2.     if(index >= element || index < 0){ 
  3.         throw new ArrayIndexOutOfBoundsException(); 
  4.     }else { 
  5.         return arr[index]; 
  6.     } 

4 根据索引删除元素删除对应索引的元素后,我们需要将所有改索引后面的元素,向前移动一位。假如我要删除索引为2的元素,如下:

 

理论上平均删除一个元素,我们需要移动N/2次,所以它的时间复杂度也为O(1)。

  1. public void delete(int index){ 
  2.     if(index >= element || index < 0){ 
  3.         throw new ArrayIndexOutOfBoundsException(); 
  4.     }else { 
  5.         for (int i = index; i < element; i++) { 
  6.             arr[index] = arr[index+1]; 
  7.         } 
  8.         element --; 
  9.     } 

2.5 修改元素

修改某个位置的元素,直接根据索引就一次就可以修改对应的元素,所以它的时间复杂度为O(1)。

  1. public void change(int index,long newValue){ 
  2.     if(index >= element || index < 0){ 
  3.         throw new ArrayIndexOutOfBoundsException(); 
  4.     }else { 
  5.         arr[index] = newValue; 
  6.     } 

三 有序数组

有序数组是数组的一种特殊类型,有序数组中的元素按照某种顺序进行排列。

3.1 添加元素

在添加元素的时候,将元素按顺序添加到某个位置。如下,在一个数组中添加一个33的元素。

 

首先,将索引为3的元素移动到索引为4的位置,然后将索引为2的元素移动到索引为3的位置,最后将33添加到索引为2的位置。理论上插入一个元素需要移动元素的个数为N/2个,所以它的时间复杂度为O(N)。

  1. public void add(long value){ 
  2.     int i; 
  3.     for (i = 0; i < element; i++) { 
  4.         if(arr[i]>value){ 
  5.             break; 
  6.         } 
  7.     } 
  8.  
  9.     for (int j = element; j > i; j--){ 
  10.         arr[j] = arr[j-1]; 
  11.     } 
  12.     arr[i] = value; 
  13.     element++; 

3.2 二分法根据元素查询索引

在无序数组中,使用线性法进行查找相关元素,线性法即按索引按个查找。有序数组可以使用二分法来查找元素,二分法是指将一个数组从中间分成两个,判断元素位于哪个数组中,然后重复这样的操作。

假如有8个元素的一个数组,数组内容为有序的0-7的序列,要查找5这个元素,第一次分成0-3和4-7两个数组,然后再将4-7分成4-5和6-7两个数组,最后再将4-5分成4和5就查询出来具体的元素了,这样分割3次就可以查询出长度为8的数组中具体的元素,其复杂度即为O(logN)(logN在计算机中底数一般指的是2,意思为2的几次方等于n)。

  1. public int search(long value){ 
  2.     // 中间值 
  3.     int middle = 0; 
  4.     // 最小值 
  5.     int low = 0; 
  6.     // 最大值 
  7.     int pow = element; 
  8.     while (true){ 
  9.         middle = (low + pow) / 2; 
  10.         if(arr[middle] == value){ 
  11.             return middle; 
  12.         }else if (low > pow){ 
  13.             return -1; 
  14.         }else
  15.             if(arr[middle] > value){ 
  16.                 pow = middle - 1; 
  17.             }else
  18.                 low = middle + 1; 
  19.             } 
  20.         } 
  21.     } 

四 总结

复杂度越低意味着算法更加优秀,所以O(1) > O(logN) > O(N) > O(N^2)。

算法 复杂度
线性查找 O(N)
二分法查找 O(logN)
无序数组插入 O(1)
有序数组插入 O(N)
无序数组删除 O(N)
有序数组删除 O(N)

 

本文转载自微信公众号「Java旅途」,可以通过以下二维码关注。转载本文请联系Java旅途公众号。

 

来源: Java旅途内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯