关键词：基础 线性 连续
数组是什么
相同类型的数据的组合。
数组是一种线性表数据结构。将一组相同类型的数据存储在连续的内存空间。
线性表: 数据最多只有前和后两个方向的数据结构（数组和链表）。
数组连续的存储空间的特点，带来的优劣势：
- 优势：“随机（直接）访问”。
- 劣势：删除、插入操作变得低效, 复杂度为O(n)。为保证连续性，需要把数据往后移。
数组各个操作的复杂度
读取 O(1)
通过下标直接访问。再次强调一遍：得益于数组连续存储的特点。
查找 O(n)
通过遍历来查找O(n) ，用二分法复杂度是O(logn)
链表更适合插入、删除，时间复杂度 O(1)。
插入 O(n)
如果是数组末尾插入元素，那复杂度会是O(1),因为不用挪数据。
当添加的位置在数组中间时，需要把位置后面的数组往后挪一个位置。因此复杂度为O(n)。
如果数组是乱序的，那就直接数组末尾插入元素。复杂度O(1)。
删除 O(n)
当删除的数据在数组末尾时，直接将数组最后的元素去除，释放资源就可以。复杂度O(1)。
当目标元素在数组中间时，先把数据拿出，然后把改数据后面的元素一个个往前推，最后释放内存。复杂度O(n)。
衍生：集合
集合就是一个带有“不允许重复”这种简单限制的数组。而该限制也导致它的 插入 与数组性能不同。多了个查找的步骤。
插入步骤：
- 查找。确定元素不存在于数组中
- 插入。就是数组的正常插入。
leetcode
写题目看看自己是否掌握了数组的特性吧。
- 11 盛最多水的容器
- 26 删除排序数组中的重复项
- 41 缺失的第一个正数
- 88 合并两个有序数组
- 169 多数元素
参考资料：《数据结构与算法题解》 《我的第一本算法书》
