简述
数组是存放在连续内存空间上的相同类型数据的集合。
也是最基础的数据结构,因为它最适应现代计算机内存结构的数据结构,也被称为"线性表结构", 几乎是所有算法学习者接触的第一个结构。
在面试中,考察数组的题目一般不需要多复杂的解题思维,主要是考察对代码的掌控能力,往往拿到数组题的时候,第一感觉就是想法思路很简单,但是基本功如果不到位的话,实现起来总会出错。
想要在面试中不在数组题上翻车,就必须要先理解数组的特性,以及什么情况下更适合使用数组作为数据结构。
数组的内存结构
因为数组是存放在连续内存空间上的相同类型数据的集合,所以可以方便的通过下标索引的方式获取到下标对应的数据。
因此,数组的创建会有两个特征:
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的
正是因为数组在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。也是数组主要的性能开销。
例如,我们从数组中删除下标为3的C。
这是基于数组的特性:数组的元素是不能删的,只能覆盖。 因此如果删除了一个元素,那么后续的所有元素都要一次平移覆盖前一个元素。 因此最坏的情况就是,如果删除的是第一个元素,那么整个数组剩下的所有元素都要进行一次平移,使得时间复杂度为O(N)。
插入也是同样的道理,如果需要在某一个下标处插入元素,且这个位置(包括之后的下标位置)已经有元素了,则该下标以及以后的所有元素都需要向后完成一次平移。 所以,当我们面对的问题如果不关注元素的顺序,或者需要频繁的插入和删除操作,那么通常意味着数组并不是理想的选择。
数组的优缺点
优点:
- 查找速度快。
- 允许快速随机访问。
缺点:
- 删除和插入效率低。
- 大小固定,不支持动态扩展
- 要求内存空间必须连续。
高维数组空间连续问题
通过在array中存放array,数组可以是多维度的, 但是很多人会有一个误区:那就是想当然地认为高维数组内存空间也是连续的,但其实并不是。以一个3*4的二维数组为例
可以看出来,二维数组在内存中不是想当然的 3*4 的连续地址空间,而是四条连续的地址空间组成。
数组是否有序
从数组的角度,可以分为有序数组和无序数组。在解数组题的过程中,首先要观察题目给出的数组,因为数组是否有序,对某些操作的性能差异很大,会直接影响我们算法的选择。
| 操作 | 有序数组 | 无序数组 |
|---|---|---|
| 下标查询 | O(1) | O(1) |
| 线性搜索 | O(N) | O(N) |
| 二分搜索 | O(log(N)) | 不支持 |
| 插入元素 (线性) | O(2N) = O(N) | O(2N) = O(N) |
| 插入元素 (基于二分) | O(log(2N)) + O(N) = O(N) | O(2N) = O(N) |
| 删除元素 | O(1) + O(N) = O(N) | O(1) + O(N) = O(N) |
| 排序 | 无需排序 | O(N^2) |
数组问题分类
因为数组作为数据结构,能够支持的操作比较有限,所以数组问题的解决方案相对比较有套路,基本上有五种解题思路。
- 模拟法
- 二分法
- 暴力解法时间复杂度:O(n)
- 二分法时间复杂度:O(logn)
- 双指针法
- 暴力解法时间复杂度:O(n^2)
- 双指针时间复杂度:O(n)
- 滑动窗口
- 暴力解法时间复杂度:O(n^2)
- 滑动窗口时间复杂度:O(n)
- 前缀和
- 暴力解法时间复杂度:O(n^2)
- 前缀和时间复杂度:O(n)
模拟类的题目在数组中很常见,不涉及到什么算法,就是单纯的模拟,十分考察大家对代码的掌控能力。
借助有序数组的条件优化暴力搜索的性能。
通过使用两个指针在一个for循环下完成两个for循环的工作。
滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。
针对于求解类似"数列的前 n 项的和"问题,采用预处理的方式减少整体时间开销。