思考:为什么数组要从 0 开始编号,而不是从 1 开始呢?
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据**
- 线性表(Linear List)
线性表就是数据排成一条线一样的结构,每个线性表上的数据最多只有前后两个方向。除了数组,链表、队列、栈也是线性表结构。
对应的概念是非线性表,如二叉树、堆、图等,数据之间并不是简单的前后关系。
- 连续的内存空间和相同类型的数据
这两点让数组有了一个重要的特性:「随机访问」。
- 优势: 下标随机访问(
⚠️ 而非查找操作)的时间复杂度是O(1) - 劣势:删除、插入等操作,为了保证连续性而变得低效
a[i]_address = base_address + i * data_type_size
数组为了保持内存数据的连续性,会导致插入、删除的操作比较低效。
- 插入操作:
- 有序
- 无序
- 删除操作:
- 标记->需时一次批量删除
- 容器的优势:
- 封装许多数组操作细节
- 支持动态扩容
对于业务开发,直接用容器就足够了;
对于底层开发,性能需要优化到极致,就要考虑优选数组了。
「下标」的定义是「偏移」
以下是从 0 开始:
a[i]_address = base_address + i * data_type_size
以下是从 1 开始:
a[k]_address = base_address + (k-1)*type_size
- 从 1 开始,每次随机访问数组元素时都多了一次减法运算。
- 最主要原因可能还是历史原因
-
初始化
-
获取长度
-
「随机访问」根据索引获取元素
-
元素遍历
-
修改元素
-
排序
- 做好初始定义
做数组类算法问题的时候,常常需要定义一个变量,明确该变量的定义,并且在整个算法逻辑中,不停地维护住这个变量的定义,特别注意初始值和边界的问题。
- 运用基础算法思想
典型的排序算法思想、二分查找思想在数组中应用非常广泛
- 双索引技巧 - 对撞指针
对撞指针:指针 i 和 j 分别指向数组的第一个元素和最后一个元素,然后指针 i 不断向前,指针 j 不断递减向后,直到 i = j。
- 双索引技巧 - 滑动窗口
一些题目利用「滑动窗口」方法,可以将时间复杂度控制在 O(n) 级别。定义好滑动窗口,明确表达的意思,并考虑边界与初始值。