数据结构与算法篇- 「数组」

数组，一个程序员熟悉的不能再熟悉的数据结构了，可以说在我们的日常开发中，到处都有它的身影，就是这么一个我们熟悉的数据结构，我们对它真的了如指掌了吗？

1. 什么是数组？
   数组是线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。它的最重要的特点就是连续内存空间 相同类型的数据。
   常见的线性表结构还有，栈、队列、链表。
   常见的非线性表结构有，树、堆、图等。

2. 大家常说的 「 数组适合查找，查找的时间复杂度为O(1) 」，这句话正确吗？
   并不准确，正确的说法，应该为 数据支持随机访问，根据下标随机访问的时间复杂度为O(1)，但如果是根据 元素值 去查询的话，就不再是O(1)了，而是由 数组是否有序以及你所使用的排序方法来决定的了。

3. 为什么说 数组的插入、删除操作是低效的？
   数组是需要连续内存的，插入和删除操作都需要位移操作下标之后的数据源。比如数组a的长度为n，我们需要在下标为k的位置插入一个元素，那么下标k至n的元素都需要往后迁移一位。删除也是同理。
   如果在下标n插入一个元素，时间复杂度为O(1)
   在下标1插入一个元素，时间复杂度为O(n)
   在下标为k的位置插入，时间复杂度为O(n-K+1)
   由于在每个位置插入的概率都是相同的，那么时间平均复杂度为O(1/n * n(n-1)/2) = O(n)
   删除同理。

4. 如果是连续的删除操作，有什么可以提高效率的方法？
   我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。