# 数组

# 介绍

虽然数据结构有很多，比如树，图，哈希表，但真正实现它们的还需要落实到具体的基础数据结构，即数组和链表。之所以说他们是基础的数据结构，是因为它们直接控制物理内存的使用。

数组使用连续的内存空间，来存储一系列同一数据类型的值。如图表示的是数组的每一项都使用一个 byte 存储的情况。

那么为什么数组要存储相同类型的值呢？为什么有的语言（比如 JS）就可以存储不同类型的值呢？

实际上存储相同的类型有两个原因：

1. 相同的类型大小是固定且连续的(这里指的是基本类型，而不是引用类型，当然引用类型也可以存一个大小固定的指针，而将真实的内容放到别的地方，比如内存堆)，这样数组就可以随机访问了。试想数组第一项是 4 字节，第二项是 8 字节，第三项是 6 字节，我如何才能随机访问？而如果数组元素的大小都一样，我们就可以用基址 + 偏移量来定位任意一个元素，其中基值指的是数组的引用地址，如上图就是 1001。 偏移量指的是数组的索引。
2. 强类型语言要求指定数组的类型。

虽然在一些语言，比如 JavaScript 中，数组可以保存不同类型的值。这是因为内部做了处理，这个不在我们的讨论范围，感兴趣的可以查下相关资料。

数组的一个特点就是支持随机访问，请务必记住这一点。当你需要支持随机访问的数据结构的话， 自然而然应该想到数组。

本质上数组是一段连续的地址空间，这个是和我们之后要讲的链表的本质差别。 虽然二者从逻辑上来看都是线性的数据结构。

• 一个数组表示的是一系列的元素
• 数组（static array）的长度是固定的，一旦创建就不能改变（但是可以有 dynamic array）
• 所有的元素需要是同一类型（个别的语言除外）
• 可以通过下标索引获取到所储存的元素（随机访问）。 比如 array[index]
• 下标可以是是 0 到 array.length - 1 的任意整数

当数组里的元素也是一个数组的时候，就可以形成多维数组。例子：

1. 用一个多维数组表示坐标 array[y]
2. 用一个多维数组来记录照片上每一个 pixel 的数值

力扣中有很多二维数组的题目，我一般称其为 board。

# 数组的常见操作

1. 随机访问，时间复杂度 O(1)

arr = [1,2,33]
arr[0] # 1
arr[2] # 33

2. 遍历，时间复杂度 O(N)

for num in nums:
  print(num)

3. 任意位置插入元素、删除元素

arr = [1,2,33]
# 在索引2前插入一个5
arr.insert(2, 5)
print(arr) # [1,2,5,33]

我们不难发现， 插入 2 之后，新插入的元素之后的元素（最后一个元素）的索引发生了变化，从 2 变成了 3，而其前面的元素没有影响。从平均上来看，数组插入元素和删除元素的时间复杂度为O(N)。最好的情况删除和插入发生在尾部，时间复杂度为 O(1)。

基本上数组都支持这些方法。 虽然命名各有不同，但是都是上面四种操作的实现：

• each()： 遍历数组
• pop(index)：删除数组中索引为 index 的元素
• insert(item, index)：数组索引为 index 处插入元素

时间复杂度分析小结

• 随机访问 -> O(1)
• 根据索引修改 -> O(1)
• 遍历数组 -> O(N)
• 插入数值到数组 -> O(N)
• 插入数值到数组最后 -> O(1)
• 从数组删除数值 -> O(N)
• 从数组最后删除数值 -> O(1)

# 基本概念

• 数组交集
• 数组并集
• 数组合并

# 题目推荐

• 380. 常数时间插入、删除和获取随机元素

  • 题解地址

• 75. 颜色分类

  • 题解地址