两个数组找相同元素_认识数组

相信大家对数组都不算陌生，毕竟在大多数的编程语言里面都会存在这种数据结构。但是你知道为啥数组的下标几乎都是从 0 开始的么？

在弄清楚这个问题之前，我们先了解下数组的定义吧。

作为最基础的数据结构，数组是一种线性表结构。用一段连续的内存空间，来存储一组相同类型的元素，并且可以通过元素的索引访问存储地址。

第一个特性是线性表。

线性表是指元素最多只有前后两个方向，可以想象成一条线穿过一颗颗珠子的样子。除了数组，还有链表、队列、栈等也是线性表结构。

与之对立的就是非线性表结构，比如说树、图、堆等。表示的也是元素之间不只是前后关系。

第二个特性是连续的内存空间和相同类型的元素。

而上面提到的通过索引访问存储地址也是由于这两个限制得以实现——也被称作「随机访问」。因为内存空间的连续，保证数据元素之间一定是紧挨着的；再加上相同类型的元素，可以确定每个元素占用的空间大小是相同的。这样就可以通过寻址公式轻松访问到任意一个元素。

int

需要注意的是，数组相比于链表，前者适合查找，后者适合插入和删除，但是查找的时间复杂度不是 O(1)。更加准确的说法是，数组在随机访问下的时间复杂度才是 O(1)。

通过上面的寻址公式就可以对数组轻易的实现插入、删除操作了。

虽然相比于链表，数组的插入和删除效率比较低，但是你知道是为什么吗？

原因就是上面提到的第二个特性，由于使用了连续的内存空间，当需要对数组元素进行修改（插入、删除）时，就会涉及到元素的迁移。

假设上面数组 a 存储了 {a, b, c, d, e} 共 5 个元素，现在需要在 a[3] 位置插入元素 x，就需要把 a[3] 位置空出来，可以是把 a[3] 以及之后的元素都向后移动，也可以单独把 a[3] 元素移动到末尾。

同理，删除元素也是类似。

当然，数组的删除也可以优化。比如 JVM 的标记清除垃圾回收，当需要删除多个元素的时候，先记录下被删除的元素（做标记），等到了一定时间或者空间不够的时候，一次性触发元素的迁移动作。这样就可以大大节省迁移数据元素的时间。

另外，在 Java 语言中，还有对数组做了封装的 List 类，屏蔽了很多对数组操作的细节，比如支持动态扩容，节省了开发的时间。

同样的，有利也有弊。List 相关的类只支持基本类型的包装类，基本类型转换成包装类型是需要装箱操作的，也会消耗一定的性能；另外就是 List 相关类表示多维数组的时候没有直接使用数组来的直观。

最后，回到开篇。数组为啥是从 0 开始的？

我觉得有两个原因，一个是寻址公式中的 i 从 0 开始就会少一道减法运算，会影响性能。第二个原因是 C 语言设计的时候使用 0 开始作为数组的下标，随着语言的发展，继续沿用至今。