::: info 定义 数组（Array） 是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 :::
但在 JavaScript 里，数组中可以保存不同类型的值（大多数语言都没这个能力）。但我们还是要遵守最佳实践，别这么做。
// 一维数组：
// 数组的每一个元素是一个数据类型
[1, 2, 3]
// 二维数组：
// 数组的每一个元素是一个一维数组
[["a", "b", "c"], [1, 2, 3], 123]
// 三维数组：
// 数组的每一个元素是一个二维数组
[
[
["a", "b", "c"],
[1, 2, 3],
],
[
["a", "b", "c"],
[1, 2, 3],
],
]我们还可以从两个方面来解释一下数组的定义。
- 「线性表」
- 「连续的内存空间」
::: info 定义
线性表（Linear List） 就是数据排成像一条线一样的结构，线性表上的数据元素都是相同类型。每个线性表上的数据最多只有前和后两个方向。
:::
数组、链表、队列、栈都是是线性表结构。
线性表有两种存储结构：「顺序存储结构」和「链式存储结构」。
其中，「顺序存储结构」是指占用的内存空间是连续的，相邻数据元素之间，物理内存上的存储位置也相邻。
数组也是采用了顺序存储结构，并且存储的数据都是相同类型的。
与它相对立的是非线性表，比如二叉树、堆、图等。
在非线性表中，数据之间并不是简单的前后关系。
数据结构的操作一般涉及到增、删、改、查共 4 种情况，下面我们一起来看一下数组的这 4 种基本操作。
因为数组有连续的内存空间和相同类型的数据，所以数组支持 “随机访问”。
但这两个限制也让数组的很多操作变得非常低效，比如在数组中删除、插入一个数据，为了内存数据的保证连续性，就需要做大量的数据搬移工作。
在面试的时候，面试官常常会问数组和链表的区别？很多人都回答说，“链表适合插入、删除，时间复杂度 O(1)；数组适合查找，查找时间复杂度为 O(1)”。实际上，这种表述是不准确的。
数组适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，用二分查找，时间复杂度也是 O(logn)。
所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
- 修改指定索引位置的元素
array.splice(index, 1, item)let myArray3 = [1, 2, 3, 4, 5, 6]; // 修改 索引 1 的位置的元素为 AA myArray2.splice(1, 1, 'AA'); console.log(myArray3); //--> [1, "AA", 3, 4, 5, 6]
- 修改指定索引位置的几个元素
array.splice(index, number, item)let myArray4 = [1, 2, 3, 4, 5, 6, 7]; // 在 索引 2 的位置起，修改两个元素为 AA BB myArray2.splice(2, 2, 'AA', 'BB'); console.log(myArray3); //--> [1, 2, "AA", "BB", 5, 6, 7]
改变元素的操作跟访问元素操作类似，访问操作不依赖于数组中元素个数，因此，「改变元素」的时间复杂度为 O(1)。
- 添加一个元素到数组的最后位置
array.push(item) - 在数组首位插入一个元素
array.unshift(item) - 在指定索引位置插入元素
array.splice(index, 0, item)splice() 第二个参数为 0 时，表示插入数据。
let myArray = [1, 2, 3]; // 在 索引 0 的位置，插入 A myArray.splice(0, 0, 'A'); console.log(myArray); //--> ['A', 1, 2, 3]
假设数组的长度为 n，将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾给新来的数据，要将第 k ～ n 这部分的元素都顺序地往后挪一位。
- 如果在数组的末尾插入元素，不需要移动数据，时间复杂度为
O(1)。 - 但如果在数组的开头插入元素，那所有的数据都要依次往后移动一位，所以最坏时间复杂度是
O(n)。 - 因为每个位置插入元素的概率一样，所以平均情况时间复杂度为
(1 + 2 + … + n) / n = O(n)。
如果数组中的数据是有序的，在插入新元素时就必须搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，将某个新元素插入到第 k 个位置时，为了避免大规模的数据搬移，有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。
例如：数组 a 中存储了如下 5 个元素：a，b，c，d，e。要将元素 x 插入到第 3 个位置。只需将 c 放入到 a[5]，将 a[2]赋值为 x 即可。最后数组中的元素如下： a，b，x，d，e，c。
利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。这个处理思想在快排中也会用到。
- 删除数组最后的元素
array.pop() - 删除数组首位的元素
array.shift() - 删除指定索引位置的元素
array.splice(start, deleteCount)例如：let myArray2 = [1, 2, 3, 4, 5]; // 删除索引 3 位置起，2 个元素 myArray2.splice(3, 2); console.log(myArray2); //--> [1, 2, 3]
跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。
和插入类似：
- 如果删除数组末尾的数据，则最好情况时间复杂度为
O(1)； - 如果删除开头的数据，则最坏情况时间复杂度为
O(n)； - 平均情况时间复杂度也为
O(n)。
实际上，在某些特殊场景下，并不一定非得追求数组中数据的连续性。如果每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，再触发执行一次真正的删除操作，就可以大大减少了删除操作导致的数据搬移。这也是JVM 标记清除垃圾回收算法的核心思想。
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 189 | 轮转数组 | [✓] | 数组 数学 双指针 |
Medium |
| 66 | 加一 | [✓] | 数组 数学 |
Easy |
| 724 | 寻找数组的中心下标 | [✓] | 数组 前缀和 |
Easy |
| 485 | 最大连续 1 的个数 | [✓] | 数组 |
Easy |
| 238 | 除自身以外数组的乘积 | [✓] | 数组 前缀和 |
Medium |
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 498 | 对角线遍历 | [✓] | 数组 矩阵 模拟 |
Medium |
| 48 | 旋转图像 | [✓] | 数组 数学 矩阵 |
Medium |
| 73 | 矩阵置零 | [✓] | 数组 哈希表 矩阵 |
Medium |
| 54 | 螺旋矩阵 | [✓] | 数组 矩阵 模拟 |
Medium |
| 59 | 螺旋矩阵 II | [✓] | 数组 矩阵 模拟 |
Medium |
| 289 | 生命游戏 | [✓] | 数组 矩阵 模拟 |
Medium |