《2-数组》

数组

1.简介：

数组（Array）是一种固定长度的存储相同数据类型在连续内存空间中的数据结构

引出：[索引 （Index）]----元素在数组中的位置

2.初始化

写法：一般用到无初始值、给定初始值
在不给定初始值的情况下，通常所有元素会被初始化为默认值0

/*初始化数组*/
int[] arr=new int[5];//{0,0,0,0,0}
int[] nums={1,3,2,5,4}; 

3.优点：
在数组中访问元素非常高效
给定数组首个元素的地址和一个元素的索引，利用以下公式可以直接计算得到该元素的内存地址，从而直接访问此元素

公式：元素内存地址=数组内存地址+元素长度*元素索引（elementAddr=firtsElementAddr+elementLength*elementIndex）

4.缺点：

数组在初始化后长度不可变
由于系统无法保证数组之后的内存空间是可用的，因此数组长度无法扩展
而若希望扩容数组，则需新建一个数组，然后把原数组元素依次拷贝到新数组，在数组很大的情况下非常耗时

/*扩展数组长度*/
int[] extend(int[] nums,int enlarge){//初始化一个扩展长度后的数组int[] res=new int[nums.length+enlarge];//将原数组中的所有元素复制到新数组for(int i=0;i<nums.length;i++){res[i]=nums[i];} //返回扩展后的新数组return res; 
}

数组中插入或删除元素效率低下
如果我们想要在数组中间插入一个元素，由于数组元素在内存中是“紧挨着的”，它们之间没有空间再放任何数据

因此，我们不得不将此索引之后的所有元素都向后移动一位，然后再把元素赋值给该索引

/*在数组的索引 index处插入元素 num*/
void insert(int[] nums,int num,int index){//把索引 index以及之后的所有元素向后移动一位for(int i=nums.length-1;i>index;i--) nums[i]=nums[i-1];//将 num赋给 index处元素nums[index]=num; 
}

删除元素也是类似，如果我们想要删除索引i处的元素，则需要把索引i之后的元素都向前移动一位。
值得注意的是，删除元素后，原先末尾的元素变得“无意义”了，我们无需特意去修改它;

/*删除索引index处元素*/
void remove(int[] nums,int index){//把索引 index之后的所有元素向前移动一位for(int i=index;i<nums.length-1;i++) nums[i]=nums[i+1];
}

总结来看，数组的插入与删除操作有以下缺点:
●时间复杂度高:数组的插入和删除的平均时间复杂度均为O(N)，其中N为数组长度
●丢失元素:由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会被丢失
●内存浪费:我们一般会初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是我们不关心的，但这样做同时也会造成内存空间的浪费

5.常用操作：

数组遍历

以下介绍两种常用的遍历方法：

/*数组遍历*/
void traverse(int[] nums){int cnt=0;//通过索引遍历数组for(int i=0;i<nums.length;i++) cnt++;//直接遍历数组for(int num:nums) cnt++;
} 

数组查找

通过遍历数组，查找数组中的指定元素，并输出对应索引

/*在数组中查找指定元素*/
void find(int[] nums,int target){for(int i=0;i<nums.length;i++)if(nums[i]==target) return i;return -1;
} 

6.典型应用：

随机访问；如果我们想要随机抽取一些样本， 那么可以用数组存储，并生成一个随机序列，根据索引实现样本的随机抽取

二分查找；例如查字典的例子，我们可以将字典中的所有字按照拼音顺序存储在数组中，然后使用与日常查纸质字典相同的“翻开中间，排除一半” 的方式，来实现一一个查电子字典的算法

//做笔记的美好的一天