数据结构和算法第二讲 - 数组
本讲内容：
数组定义
数组特点
应用场景
简单算法题
数组定义
定义：数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
数组特点
1. 数据有前后关系
线性表
线性：数据元素有前后顺序，如数组，链表，栈，队列
非线性：如树，图，堆
2. 随机访问
数组支持随机访问的原因是因为数组有连续的内存空间和存储相同类型的数据
3. 插入删除低效
- 插入
最好O(1) 最坏O(n) 平均O(n)
数组若无序，插入新元素时，可以将第k个位置元素移动到数组末尾，把新元素插入到第k个位置，此处复杂度为O(1)。
数组若有序，插入新元素时，如果新元素小于最大元素，则需要移动前面的数组元素（此处假设数组有序递增） - 删除
最好O(1) 最坏O(n) 平均O(n)
删除操作需要搬移元素，保证内存的连续性，因此可以把多次删除操作合并在一起进行操作，减少搬移次数，提升性能。
TODO：学习JVM垃圾回收机制对于删除垃圾元素的做法
4. 数组的访问越界问题
访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。
TODO:
为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？
从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。
如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：
a[k]_address = base_address + k * type_size
但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：
a[k]_address = base_address + (k-1)*type_size
对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。
数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。
除此之外，更重要的是历史原因，最开始C 语言设计者用 0 开始计数数组下标，后来JAVA等语言的设计者也就效仿C语言，从0开始了。
应用场景
业务场景可以使用容器类数组
底层的开发建议都使用数组
简单算法题
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
