7.数组：如何实现基本索引的查找

数组可以看成是线性表的一种推广，属于另一种基本的数据结构

7-1 什么是数组

数组是数据结构中最基本结构，几乎所有语言都会把数组类型设定为固定的基础变量类型
可以把数组理解为一种容器，它可以存放若干个相同类型的数据元素

• 存放的数据是整数型的数组，称作整型数组
• 存放的数据是字符型的数组，则称作字符数组
• 另一类特殊的数组：数组的数组，也可以叫做二维数组

用数学的方式来看，普通数组就是一个向量，二维数组就是一个矩阵
数组可以把具有相同类型的元素以不同规则顺序进行排列，这些排列好的同类数据元素集合被称为数组
数组的内存是连续存放的，数组内的数据，可以通过索引直接取出得到
实际上数组的索引就是对应数组空间，所以在进行增删查操作时，可以根据代表数组空间位置的索引值进行

7-2 数组的基本操作

• 数组在存储数据时是按照顺序存储的，且内存连续，这就造成它增删困难，但是查找特别容易的特点
• 相比栈和队列，只能在特定位置增删，数组就没有这些限制，可以在任意位置

7-2-1 数组的新增操作

数组新增数据有两种情况：

• 第一种情况，在数组的最后增加一个新的元素；此时新增一条数据后，对原数据没有任何影响。可以直接通过新增操作，赋值或插入一条数据即可。时间复杂度为O(1)
• 第二种情况，如果在数组中间的某个位置新增数据，就完全不一样；新增数据后，对插入元素位置之后的元素产生影响，这些数据位置需要依次向后挪动一个位置

例子：长度为4的数组，在第二个元素之后插入一个元素，修改后的数组就包含了5个元素，其中1，2元素不发生变化，第三个是新来的元素，第4、5 个元素是原来的3、 4 元素。这个搬家操作，与数据量线性相关，时间复杂度为O(n)

7-2-2 数组的删除操作

数组删除数据有两种情况：

• 第一种情况，在数组的最后删除一个数据元素；此时删除一条数据后，对原数据没有任何影响。可以直接删除即可，时间复杂度为O(1)
• 第二种情况，如果在数组中间的某个位置删除数据；删除数据后，该元素位置之后的元素产生影响，这些数据位置需要依次向前挪动一个位置

7-2-3 数组的查找操作

• 数组的查找操作，由于有了索引的存在，数组基于位置的查找比较容易实现，可以通过索引找到元素，此时时间复杂度为O(1)
  

例如：查找数组中第三个位置的元素，直接a[2] 就可以直接取出来；但对于链表系的数据结构，是没有这个优势的

• 但是另一种查找，如查找某一个数值为多少的元素时，数组就没有优势了，也需要整体遍历数组，都需要O(n)的时间复杂度
  

上面的操作，都已经有封装了，新增：push(),unshift(),concat(),splice();删除：pop(),shift(),slice();查找：indexOf(),lastIndexOf(),

• 但是不要被迷惑了，即使是封装好的函数，时间复杂度也不会发生改变，依然是底层的分析结果。

7-3 数组增删查操作的特点

数组的增删查比栈和队列相比，方法更多，操作更灵活，下面我们来归纳一下数组增删查的时间复杂度：

• 增加：若插入数据在最后，则时间复杂度为O(1);若在中间插入，则为O(n)
• 删除：在末尾删除，时间复杂度为O(1);若在中间删除，则为O(n)
• 查找：若根据索引查找，则时间复杂度为O(1);若在数组中查找一个数值满足指定条件的数据，则时间复杂度为O(n)

实际上数组是一种相当简单的数据结构，其增删查的时间复杂度对于链表来说整体更优，那么链表存在意义在哪？

• 1.首先，链表的长度是可变的，数组长度是固定的，在申请数组长度时就已经在内存中开辟了若干空间。如果没有引用ArrayList时，数组申请空间永远是我们在估计了数据大小后才执行，所以后期维护中也相当麻烦

• 2.其次，链表不会根据有序位置存储，在插入元素时，可以用指针充分利用内存空间。数组是有序存储的，如果想充分利用内存空间就只能选择顺序存储，且需要不取数据，不删除数据的情况下才能实现

7-4 数组的案例

例题：假设数组存储了5个评委对1个运动员的打分，且每个评委的打分都不相等，现在需要

• 1.用数组按照连续顺序保存，去掉一个最高分和最低分后的三个打分样本
• 2.计算这三个样本的平均分并打印

要求是：不允许再开辟O(n)空间复杂度的复杂数据结构
分析：由于不能再开辟新的复杂空间，因此只能在原数组中找到最大和最小值；删除最小最大值后，计算平均值；解法如下：

• 数组一次遍历，过程中记录下最小值和最大值索引，时间复杂度是O(n)
• 执行两次索引值的删除操作，非极端情况，则时间复杂度为O(n)
• 计算删除数据后的数组元素平均值，时间复杂度为O(n)

通过计算，三次数据处理的总复杂度，依然是O(n)

 function s7_1(){
   let a = [1,3,8,5,2];
   let min_index = -1;
   let max_index = -1;
   let min_val = 99;
   let max_val = -1;
   let index1,index2;
   // 第一步：找到最大值最小值及对应的index索引
   for(let i = 0; i < a.length;i++){
     if(a[i] > max_val){
       max_val = a[i];
       max_index = i;
     };
     if(a[i] < min_val){
       min_val = a[i];
       min_index = i;
     }
   };
   //赋值，将最大值和最小值中靠后的索引index赋值给 index1,小的赋值给index2
   index1 = max_index;
   index2 = min_index;
   if(max_index < min_index){
     index1 = min_index;
     index2 = max_index;
   };
   console.log(max_index,min_index,index1,index2)
   //先处理靠后的数据，删除index1索引对应的值
   for(let j = index1; j < a.length - 1;j++){
     a[j] = a[j+1];
   };
   console.log(a)
   //再处理靠前的数据，删除index2索引对应的值
   for(let k = index2; k < a.length - 1;k++){
     a[k] = a[k+1];
   };
   console.log(a)
   let comput = 0;
   // 剩下的3个值相加
   for(let m = 0; m < a.length - 2;m++){
     comput += a[m];
   }
   console.log(comput)
   // 求平均值
   let rel = comput / 3.0;
   console.log(rel)
   return rel;
 }

7-5 总结

• 实际操作中，我们要注意数组的优缺点合理区分数组和链表的使用
• 数组定义简单，访问方便，但是数组中的元素类型必须一致，且长度在定义时就要给出，且使用内存空间必须连续
• 数组更适合数量确定，较少甚至不需要新增，删除数据的场景下使用，比如高频按照索引查找数据时，数组就是一个很好的选择