我认为暂且可以把「数组」分为两大类一类是「静态数组」一类是「动态数组」。本章的内容就是带大家仅仅使用最原始的静态数组自己实现一个动态数组实现增删查改的常见 API。以后你在使用标准库提供的数据结构时就知道它们的底层运行原理了。1、我们知道这块内存空间的首地址数组名arr就指向这块内存空间的首地址。2、我们知道了每个元素的类型比如 int也就是知道了每个元素占用的内存空间大小比如一个 int 占 4 字节32 bit。3、这块内存空间是连续的其大小为10 * sizeof(int)即 40 字节。所以我们获得了数组的超能力「随机访问」只要给定任何一个数组索引我可以在 O(1)O(1) 的时间内直接获取到对应元素的值。因为我可以通过首地址和索引直接计算出目标元素的内存地址。计算机的内存寻址时间可以认为是 O(1)O(1)所以数组的随机访问时间复杂度是 O(1)O(1)。数据结构的职责就是增删查改1.静态数组增加元素这就有些复杂了需要分情况讨论。情况一数组末尾追加append元素// 大小为 10 的数组已经装了 4 个元素int arr[10];for (int i 0; i 4; i) {arr[i] i;}// 现在想在数组末尾追加一个元素 4arr[4] 4;// 再在数组末尾追加一个元素 5arr[5] 5;// 依此类推// ...可以看到由于只是对索引赋值所以在数组末尾追加元素的时间复杂度是 O(1)O(1)。情况二数组中间插入insert元素// 大小为 10 的数组已经装了 4 个元素int arr[10];for (int i 0; i 4; i) {arr[i] i;}// 在索引 2 置插入元素 666// 需要把索引 2 以及之后的元素都往后移动一位// 注意要倒着遍历数组中已有元素避免覆盖不懂的话请看下方可视化面板for (int i 4; i 2; i--) {arr[i] arr[i - 1];}// 现在第 3 个位置空出来了可以插入新元素arr[2] 666;情况三数组空间已满连续内存必须一次性分配分配完了之后就不能随意增减了。只能重新申请一块更大的内存空间把原来的数据复制过去再插入新的元素这就是数组的「扩容」操作。// 大小为 10 的数组已经装满了int arr[10];for (int i 0; i 10; i) {arr[i] i;}// 现在想在数组末尾追加一个元素 10// 需要先扩容数组int newArr[20];// 把原来的 10 个元素复制过去for (int i 0; i 10; i) {newArr[i] arr[i];}// 释放旧数组的内存空间// ...// 在新的大数组中追加新元素newArr[10] 10;动态数组动态数组是静态数组的强化版也是我们在实际软件开发或者写算法题时最常用的数据结构之一。动态数组底层还是静态数组只是自动帮我们进行数组空间的扩缩容并把增删查改操作进行了封装让我们使用起来更方便而已。// 创建动态数组// 不用显式指定数组大小它会根据实际存储的元素数量自动扩缩容vectorint arr;for (int i 0; i 10; i) {// 在末尾追加元素时间复杂度 O(1)arr.push_back(i);}// 在中间插入元素时间复杂度 O(N)// 在索引 2 的位置插入元素 666arr.insert(arr.begin() 2, 666);// 在头部插入元素时间复杂度 O(N)arr.insert(arr.begin(), -1);// 删除末尾元素时间复杂度 O(1)arr.pop_back();// 删除中间元素时间复杂度 O(N)// 删除索引 2 的元素arr.erase(arr.begin() 2);// 根据索引查询元素时间复杂度 O(1)int a arr[0];// 根据索引修改元素时间复杂度 O(1)arr[0] 100;// 根据元素值查找索引时间复杂度 O(N)int index find(arr.begin(), arr.end(), 666) - arr.begin();