【算法与数据结构 07】数组 —— 数组的基本操作( 增删查与时间复杂度的关系！)

一、白话数组

数组是数据结构中的最基本结构，几乎所有的程序设计语言都把数组类型设定为固定的基础变量类型。而且数组还是其它数据结构的底层容器，比如我们前面学过的顺序列表、顺序栈等，其底层都是由数组来实现的。

我们可以把数组理解为一种容器，它可以用来存放若干个相同类型的数据元素。比如：

• 存放的数据是整数型的数组，称作整型数组；
• 存放的数据是字符型的数组，则称作字符数组；
• 另外还有一类数组比较特殊，它是数组的数组，也可以叫作二维数组。

如果用数学的方式来看，我们可以把普通的数组看成是一个向量，那么二维数组就是一个矩阵。不过，二维数组对数据的处理方式并没有太多特别之处。

数组有一个很重要的特性：数组在内存中是连续存放的，数组内的数据，可以通过索引值直接取出得到。

二、增删查操作

数组在存储数据时是按顺序存储的，并且存储数据的内存也是连续的，这就造成了它具有增删困难、查找容易的特点。

（1）数组的新增操作

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

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

（2）数组的删除操作

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

• 第一种情况，在这个数组的最后，删除一个数据元素。由于此时删除一条数据后，对原数据没有产生任何影响。我们可以直接删除该数据即可，时间复杂度是 $O(1)$。
• 第二种情况，在这个数组的中间某个位置，删除一条数据。情况与新增操作高度相似，时间复杂度为$O(n)$。

这两种情况的区别在于，删除数据之后，其他数据的位置是否发生改变。

（3）数组的查找操作

相比于复杂度较高的增删操作，数组的查找操作就方便一些了。由于索引的存在，数组基于位置的查找操作比较容易实现。我们可以索引值，直接在 $O(1)$时间复杂度 内查找到某个位置的元素。

例如，查找数组中第三个位置的元素，通过 a[2] 就可以直接取出来。但对于链表系的数据结构，是没有这个优势的。需要注意的是，数组的索引是从0开始的。所以第一个元素是a[0]，依次类推。

总的来说，如果只需根据索引值进行一次查找，时间复杂度是 $O(1)$。但是要在数组中查找一个数值满足指定条件的数据，则时间复杂度是 $O(n)$。

三、真题实例

题目：
给定一个整数类型的数组 nums，要求编写一个能够返回数组 “中心索引” 的方法。数组的 中心索引 是这样定义的：数组中心索引的左侧所有元素相加的和 = 右侧所有元素相加的和。
要求：
如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

这道题是一个面试真题，题目很简单，但是要在有限时间内想到最优解，也是具有一点挑战性的！

下面给出两种解法：两种解法的时间复杂度是不一样的，聪明的你，能不能看出那一种方法更优秀？可以在评论区留言～

解法一：

class Solution {
public: int pivotIndex(vector<int>& nums) { for(int i=0; i<nums.size(); i++){ //初始化 int sum1=0,sum2=0; //计算左边元素总和 for(int j=0; j<i; j++) sum1+=nums[j]; //计算右边元素总和 for(int k=i+1; k<nums.size(); k++) sum2+=nums[k]; if(sum1==sum2){ return i;  //返回中心索引 } } return -1; //不存在中心索引，则返回-1 }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

解法二：

class Solution {
public: int pivotIndex(vector<int>& nums) { int sum=0, sum1=0, sum2=0; //计算数组总和 for(int i=0; i<nums.size(); i++) sum += nums[i]; //寻找第一个中心索引 for(int i=0; i<nums.size(); i++){ sum2 = sum - nums[i] - sum1; //右边累计和 if(sum1==sum2) return i; sum1 += nums[i]; //左边累计和 } return -1; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

四、相关推荐

【C++养成计划】深入数组和字符串（Day8）

【C++养成计划】动态数组 —— 快速上手 STL vector 类（Day14）

【LeetCode 面试45】排序专题——把数组排成最小的数（详解）

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/108360908