惨遭数组滑铁卢，面试官建议回村养猪。

朴灿烈づ我的快乐病毒、 2022-09-07 05:00 52阅读 0赞

大家好呀，我是蛋蛋。瞎起题目的嘴强王者，乱写界的无冕之王。

提到数组，想必臭宝们都不陌生。说不定已经昂起脑瓜抖着腿，小眼神儿斜着来一句：“就那个随随便便用脚趾甲就能学会的数组？”

数组，你确定很简单？

自信点，语气肯定点，数组确实很简单。

但是我还要讲。

。。。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70][]

!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/18d85762259245d5b553be65d12d809d.png)

数组，一种基础的的线性数据结构。不管写什么代码基本上都会用到数组，它也是面试中面试官喜欢提问的高频问题。

鉴于它劳模的身份，**对数组的考察基本都是考察代码方面**的问题。

但是万变不离其宗，解决数组方面问题的万能钥匙，其实就是深刻的认识数组本身的深浅

![9c8b6d4635b248048ea4f00c61af0eaf.png][]

### 什么是数组？ ###

首先什么是数组？

数组是一种基础的**线性数据结构**，它是用**连续的一段内存空间，来存储相同数据类型**数据的集合。

这里面有两个重点：

*  线性数据结构
 *  连续内存存储相同数据类型

#### 线性数据结构 ####

线性数据结构，顾名思义，像线一样的数据结构，又硬又直的典型代表。

![d68f635da66c4ba19e7b0f5a42d6923f.png][]

**线性数据结构是有限的，它是某类元素的集合并且记录着元素之间的一组顺序关系，除了首尾之外，其余元素之间有且只有一个前驱和后继。**

除了数组以外，像单链表、栈、队列等也是典型的线性数据结构。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70 1][]

#### 连续内存存储的相同数据类型 ####

以一个长度为 6 的 int 类型的数组为例，理解一下“连续内存存储相同数据类型”数组的样砸。

![8bca957b4f624eb28373fb6faf1c3ba9.png][]

上图中的计算机给数组 a 分配了一块连续的内存空间 1000 - 1005，首地址 address\[0\] = 1000。

因为连续，且对于数组来说下标从 0 开始的，所有对于数组中的每个元素来说，它的内存地址就很好计算：

address[i] = address[0] + i

### 数组的操作 ###

从上面可以看出，连续内存存储使得数组有一个天然的优势，这个优势就是可以**根据下标，快速的随意访问任意一个位置的数组元素。**

因为数组可以保证不管你访问哪个元素，只要给出下标，只需进行一次操作，就可以定位到元素的位置，从而拿出这个位置上的值。

这步操作的时间复杂度就是 O(1)。

当然 God 是公平的，**在查找上让数组当了快男，那必定让它在插入和删除上加上“持久”技能点。**

在这你要明白，持久意味着花的时间多（低效）。这么看来，在数据结构与算法中，秒男成了褒义词。

![c592d7e0044f4bc6a772044a910352e5.png][]

这种插入和删除的“持久”，是如何产生的呢？

这还是要从“连续内存存储”上找原因，真所谓快也它，慢也它。

**连续的内存使得在插入或者删除的元素的时候，其它元素也要相应的移动。**

比如我们在下标为 2 的位置上插入一个元素 29：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70 2][]

为了保持连续内存存储，在下标为 2 的位置上插入 29，原先 2 - 5 下标位置上元素都要向后一步走，可以看出这一步操作的时间复杂度为 O(n)。

当然在这我必须要强调一点的是，插入的时间复杂度其实根据情况的不同而不同，在这里主要因为 懒 手疼，没有都列出来，毕竟我的臭宝们是最聪明哒。

一般我都是按照**最坏情况时间复杂度**来算。对于插入来说，最好的情况肯定是插在末尾，这样所有的元素都不用动，时间复杂度为 O(1)，那最坏的情况就是在数组的开头插入，这样所有的元素都要动，时间复杂度就成了 O(n)，请大家一定要注意。

![73e7e8d464924549a4e47f69a9675cc7.png][]

对删除来说，和插入操作也差不多，比如我们删除下标为 2 位置上的元素。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70 3][]

删除了下标 2 位置上的数字 a\[2\]， 原来下标 3 - 5 位置上的元素统统向前一步走。

同样对于删除来说，最好情况是删除末尾的元素，时间复杂度为 O(1)，最坏的情况是删除首位的元素，时间复杂度是 O(n)。

数组的查找、插入和删除这 3 个操作讲完以后，还有最后一点提醒一下大家，在做数组类问题的时候要注意**数组越界**的问题。

数组越界，简单来说就是对于一个大小为 n 的数组，它的下标应是 0 到 n-1，对这 n 个位置的元素之外的访问，就是非法的，这就叫做“越界”。

比如对于下面这两行代码：

lst = [1,2,3,4]
    print(lst[4])

编译一下，就会提示 IndexError : list index out of range。

臭宝们平时写数组的时候一定要注意，不然一不小心就 out 了。

![56112ae44ff742e796c75a0f36944736.png][]

![f6d0adbe6e8447e0992173302cf31637.png][]

到这里，简单的数组就讲完啦，能忍着看到这的都是真爱呀。码字码的手都痛啦，**一键三连么么哒**给我刷起来～

我是蛋蛋，咱们评论区见～

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70]: /images/20220829/a191f373d142439d9d610e2c0da55d23.png
[9c8b6d4635b248048ea4f00c61af0eaf.png]: /images/20220829/81f096f9bf5c40438cda811adcc95475.png
[d68f635da66c4ba19e7b0f5a42d6923f.png]: /images/20220829/7caaf7468af540b99071da6c12492000.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/367922974fdf46468d86ff5369e5d499.png
[8bca957b4f624eb28373fb6faf1c3ba9.png]: /images/20220829/dab7a227e4a6452fba31a1b7df0b6743.png
[c592d7e0044f4bc6a772044a910352e5.png]: /images/20220829/fd8d09d960c84e909b67f19853bb7729.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/a52f668196004334bc65089fa5cd3008.png
[73e7e8d464924549a4e47f69a9675cc7.png]: /images/20220829/1851b27ec68542dbb5a1770c876b2451.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70 3]: /images/20220829/9273ae7289134494aeead80c9222e1d7.png
[56112ae44ff742e796c75a0f36944736.png]: /images/20220829/4d47bcca885f478d9ae54706aafbffc9.png
[f6d0adbe6e8447e0992173302cf31637.png]: /images/20220829/c0c576379dce433e80463154e381fc13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70 4]: /images/20220829/d9b3dcb0cab84208b319e731f45fa86f.png