教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是 AlgoNote「算法通关手册」中 数组基础 的深度解读。文章以数组的定义与内存模型为起点系统讲解随机访问的寻址原理、多维数组的组织方式、不同编程语言中的实现差异并结合仓库源码与配套题解带读者完整掌握数组「增、删、改、查」四类基本操作及其时间复杂度为后续学习排序、二分查找、双指针、滑动窗口等数组进阶算法打下坚实基础。1. 数组是什么线性表与连续内存空间的结合1.1 数组定义数组Array是一种线性表数据结构它利用一段连续的内存空间存储一组相同类型的数据。简而言之数组是「线性表顺序存储结构」的典型代表。以整数数组为例假设数组包含 $n$ 个元素每个元素都有唯一的下标索引范围从 $0$ 到 $n - 1$每个下标对应一个数据元素。数组在计算机中本质上是一段连续的内存区域每个元素占用相同大小的存储单元这些单元都有自己的内存地址并且在物理内存中依次排列。正因为「连续」与「同构」这两个特性数组才能通过简单的地址计算实现高效的随机访问。1.2 从「线性表」视角理解数组线性表是一种数据元素顺序排列、类型相同的数据结构每个元素最多只有前驱和后继两个相邻元素。数组正是线性表的一种典型实现。除了数组之外栈、队列、链表等也属于线性表结构它们在逻辑上都呈现一维有序的特征区别主要在于物理存储方式与操作限制。1.3 从「存储结构」视角理解数组线性表有「顺序存储」和「链式存储」两种方式顺序存储要求内存空间连续相邻元素在物理内存中紧挨着。数组采用的就是这种方式且所有元素类型一致因此每个元素占用的存储单元大小相同可以直接用「首地址 偏移量」定位。链式存储不要求物理连续通过指针或引用把逻辑相邻的元素串联起来如链表代价是额外的指针开销与更慢的随机访问。综合两个角度数组 采用顺序存储结构实现的线性表。这也是它在随机访问上优于链表、在插入删除上劣于链表的内在原因。2. 随机访问的原理寻址公式数组最显著的特点是支持随机访问可以通过下标直接定位并访问任意一个元素而无需从头遍历。那么计算机是如何做到这一点的数组在内存中被分配为一段连续空间第一个元素的地址称为首地址记为base。每个元素类型一致、占用字节数相同记为size。访问下标为 $i$ 的元素时通过寻址公式直接计算其内存地址下标 $i$ 的元素地址 首地址 $i$ × 单个元素占用的字节数即addr(nums[i]) base i * size由于地址计算只涉及一次乘法与一次加法与数组长度 $n$ 无关因此随机访问的时间复杂度恒为 $O(1)$。这也是数组在需要频繁按下标取值的场景如排序中的比较、二分查找中的取中值中被广泛使用的原因。需要强调的是这里的 $O(1)$ 针对的是按下标访问如果要求查找某个值为 $val$ 的元素由于不确定目标位置仍需线性遍历复杂度为 $O(n)$详见下文 5.2 节。3. 多维数组数组的数组前面介绍的是只有一个维度的数组称为一维数组每个数据元素通过单一下标访问。但在实际应用中许多数据具有二维或多维结构如图像像素、矩阵、表格一维数组无法满足需求因此引入了多维数组。以二维数组为例它由 $m$ 行 $n$ 列的数据元素组成本质上可以理解为「数组的数组」——第一维表示行第二维表示列每个元素本身也是一个数组一维数组。在内存中二维数组通常采用两种方式排布行优先Row-major先存完第一行再存第二行……C / C、Python嵌套 list等多数语言默认行优先。行优先下元素matrix[i][j]的地址 首地址 (i * n j) * size。列优先Column-major先存完第一列再存第二列……Fortran 等语言采用列优先。二维数组常被视为矩阵用于处理矩阵转置、矩阵加法、矩阵乘法等问题。仓库配套题解中的 0048. 旋转图像、0054. 螺旋矩阵、0498. 对角线遍历 正是以二维数组/矩阵为载体考察下标映射规律的经典题目。4. 不同编程语言中数组的实现差异数组的连续存储、同类型定义在不同语言中落地程度不同。理解差异有助于避免跨语言移植时的认知错位。4.1 C / C最贴合定义的数组C / C 语言中的数组实现最贴合数据结构教材中对数组的定义使用一块连续的内存空间存储相同类型的数据元素无论是基本数据类型还是结构体、对象都按连续方式排列。多维数组采用行优先连续排布例如int arr[3][4] {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}};由于 C/C 数组退化为指向首元素的指针且不自动记录长度下标越界属于未定义行为需要程序员自行保证0 i n。4.2 Java连续存储但支持不规则数组Java 的数组同样存储相同类型数据底层连续存储并自带长度属性length下标越界会抛出ArrayIndexOutOfBoundsException。与 C/C 不同的是Java 的多维数组本质是「数组的数组」允许创建不规则数组jagged array即每个嵌套数组的长度可以不同int[][] arr new int[3][]; arr[0] new int[]{1, 2, 3}; arr[1] new int[]{4, 5}; arr[2] new int[]{6, 7, 8, 9};4.3 Python用 list 充当数组原生 Python 中并不存在严格意义上的「数组」数据结构最常用的是列表list功能类似于 Java 的ArrayList。与经典数组相比Python list 有以下特点可以存储不同类型的数据元素长度可以动态变化本质是动态数组尾部追加均摊 $O(1)$扩容时整体搬移支持丰富的内置方法append、pop、insert、index等。例如arr [python, java, [asp, php], c]说明若确需同类型 紧凑内存的数值数组Python 标准库还提供了array模块与numpy.ndarray但本手册及配套算法代码均以 list 作为数组的通用载体。4.4 三种实现对比维度C / CJavaPython (list)元素类型必须相同必须相同允许不同内存布局连续连续连续动态数组实现长度固定不自动记录固定自带length动态可变下标越界未定义行为抛异常抛IndexError多维数组行优先连续排布允许不规则数组嵌套 list允许不规则5. 数组的基本操作增、删、改、查数组的基本操作主要包括四类查访问 / 查找、改改变、增插入、删删除。以下代码均使用 Python list 模拟数组完整可运行。5.1 访问元素$O(1)$访问数组中第 $index$ 个元素先检查下标是否在合法范围 $0 \le index \le len(nums) - 1$ 内合法则直接按下标取值非法则抛出异常或返回特殊值。def get_element(nums: list[int], index: int): 获取数组中指定下标的元素值 if 0 index len(nums): return nums[index] else: raise IndexError(f数组下标 {index} 超出范围 [0, {len(nums)-1}]) arr [0, 5, 2, 3, 7, 1, 6] print(get_element(arr, 3)) # 输出: 3访问操作不依赖数组中元素个数因此时间复杂度为$O(1)$。5.2 查找元素$O(n)$查找数组中元素值为 $val$ 的位置遍历数组将 $val$ 与每个元素依次比较找到返回下标遍历完未找到返回特殊值如 $-1$。def find_element(nums: list[int], val: int): 查找数组中元素值为 val 的位置 for i in range(len(nums)): if nums[i] val: return i return -1 arr [0, 5, 2, 3, 7, 1, 6] print(find_element(arr, 5)) # 输出: 1 print(find_element(arr, 9)) # 输出: -1 (未找到)当数组无序时只能采用线性查找需要遍历整个数组时间复杂度为$O(n)$。若数组有序则可改用二分查找将复杂度降到 $O(\log n)$详见仓库章节 数组二分查找一。5.3 插入元素$O(n)$在数组第 $index$ 个位置插入值 $val$先检查 $index$ 是否在 $0 \le index \le len(nums)$ 范围内扩展数组长度腾出空间将 $index$ 及其后的元素整体向后移动一位最后在 $index$ 位置写入 $val$。def insert_element(nums: list[int], index: int, val: int): 在指定位置插入元素 if 0 index len(nums): # 扩展数组长度在末尾添加一个占位元素 nums.append(0) # 将 index 及其后的元素整体向后移动一位 for i in range(len(nums) - 1, index, -1): nums[i] nums[i - 1] # 在 index 位置插入 val nums[index] val return True else: return False arr [0, 5, 2, 3, 7, 1, 6] result insert_element(arr, 2, 4) print(f插入结果: {result}) # 输出: 插入结果: True print(f插入后数组: {arr}) # 输出: [0, 5, 4, 2, 3, 7, 1, 6]注意这里用 Python 的append先扩展长度再用循环完成从后往前的元素搬移。在数组中间位置插入时移动元素次数与元素个数成正比最坏和平均时间复杂度均为$O(n)$只有在末尾追加append时才达到均摊 $O(1)$。5.4 改变元素$O(1)$将数组中第 $index$ 个元素值改为 $val$检查下标合法性后直接赋值。def change_element(nums: list[int], index: int, val: int): 修改数组中指定位置的元素值 if 0 index len(nums): nums[index] val return True else: return False arr [0, 5, 2, 3, 7, 1, 6] result change_element(arr, 2, 4) print(f修改结果: {result}) # 输出: 修改结果: True print(f修改后数组: {arr}) # 输出: [0, 5, 4, 3, 7, 1, 6]改变元素与访问元素一样通过下标直接定位无需遍历时间复杂度为$O(1)$。5.5 删除元素$O(n)$删除数组中第 $index$ 个位置的元素检查下标 $0 \le index len(nums)$ 是否合法将 $index 1$ 位置及其后的元素整体向前移动一位删除最后一个元素或更新数组长度。def delete_element(nums: list[int], index: int): 删除数组中指定位置的元素 if 0 index len(nums): # 将 index 后的元素整体向前移动一位 for i in range(index, len(nums) - 1): nums[i] nums[i 1] # 删除最后一个元素或更新数组长度 nums.pop() return True else: return False arr [0, 5, 2, 3, 7, 1, 6] result delete_element(arr, 2) print(f删除结果: {result}) # 输出: 删除结果: True print(f删除后数组: {arr}) # 输出: [0, 5, 3, 7, 1, 6]删除需要移动后续元素移动次数与数组长度相关时间复杂度为$O(n)$。5.6 操作复杂度汇总操作是否依赖下标定位是否移动元素时间复杂度访问元素是否$O(1)$改变元素是否$O(1)$查找元素无序否否$O(n)$插入元素中间是是$O(n)$删除元素是是$O(n)$这一读改写快、插入删除慢的特性决定了数组的使用策略以随机访问为主、增删尽量发生在尾部的场景适合数组频繁在中间插入删除的场景则应考虑链表见仓库章节 链表基础。6. 仓库源码印证数组是算法实现的载体在本仓库中数组不仅是数据结构章节的主题更是大量算法的直接载体。从源码结构看codes/python/01_array/ 目录集中存放了基于数组的各类经典算法实现可以作为理解数组操作与复杂度分析的活教材。6.1 基于数组的排序算法数组的随机访问能力使其成为排序算法最自然的宿主。仓库在 数组排序 章节及其后续各节中逐类展开源码实现包括冒泡排序array_sort_bubble_sort.py对数组未排序区间[0, n - i - 1]的元素做相邻比较与交换并设置flag标志位若某趟未发生任何交换则提前终止——体现了就地修改数组元素改变操作 $O(1)$的组合使用。快速排序array_sort_quick_sort.py以partition哨兵划分为核心通过nums[i], nums[j] nums[j], nums[i]这类下标交换在数组上完成元素重排再递归处理左右子区间深刻依赖数组按下标随机访问的能力。此外还有选择、插入、希尔、归并、堆、计数、桶、基数排序等完整实现全部以list为数组载体见 codes/python/01_array/。6.2 数组上的查找与区间算法在掌握基本操作之后数组相关的进阶算法也全部围绕下标 区间展开二分查找利用随机访问 $O(1)$ 在有序数组上以 $O(\log n)$ 完成查找见 数组二分查找一双指针利用两个下标在数组上完成首尾相向或快慢同步遍历见 数组双指针滑动窗口本质是用两个指针维护连续子区间将嵌套循环优化为单循环见 数组滑动窗口。7. 练习题目与进阶路径7.1 配套练习题数组基础部分的配套练习覆盖基本操作、二维数组下标规律、区间处理三个方向仓库均提供完整题解建议按顺序刷完0066. 加一用数组模拟整数加一与进位本质是改变 边界进位的综合练习简单0724. 寻找数组的中心下标前缀和思想的入门题两次遍历求左右侧和简单0189. 轮转数组三次数组翻转完成原地轮转空间复杂度 $O(1)$中等0048. 旋转图像二维数组下标映射规律原地旋转 90°中等0054. 螺旋矩阵按顺时针边界模拟遍历二维矩阵中等0498. 对角线遍历按行号 列号奇偶性找规律并处理边界中等。更完整的数组分类题目清单含数组操作、前缀和、双指针、滑动窗口、二分查找等子类见 数组基础题目列表。7.2 本章延伸章节数组基础是 数组章节 的起点后续按学习路径依次展开数组排序 及其后的冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数排序各章数组二分查找一 与 数组二分查找二数组双指针 与 数组滑动窗口。总结数组是一种基础且重要的数据结构采用连续内存存储同类型数据最大优势在于支持随机访问通过寻址公式「首地址 下标 × 元素字节数」即可在 $O(1)$ 时间内定位任意元素。数组的访问与修改操作时间复杂度为 $O(1)$插入与删除因需要移动元素而为 $O(n)$。掌握这一读快写慢的特性是理解排序、二分查找、双指针、滑动窗口等一切数组算法的基础也是后续学习链表、栈、队列等线性结构时进行横向对比的锚点。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐Zstandard Seekable Format 深入解析基于 zstd 1.5.7 的可寻址压缩与随机访问实践Zstandard Seekable Format 深入解析基于 zstd 1.5.7 的可寻址压缩与随机访问实践 Zstandard Seekable Fo可观测性日志分析云原生流处理终极Windows组策略解锁指南让家庭版也能享受专业级系统控制终极Windows组策略解锁指南让家庭版也能享受专业级系统控制 你是否曾经对着Windows家庭版电脑叹气羡慕专业版用户能随意调整系统策略Policy P桌面应用MongoDB 仓库中 zstd 可寻址格式Seekable Format深度解析帧切分、跳表结构与随机访问解压实战MongoDB 仓库中 zstd 可寻址格式Seekable Format深度解析帧切分、跳表结构与随机访问解压实战 本文以 MongoDB 仓库内嵌的数据库文档数据库后端上一篇Polymer/lit-element 入门指南从零开始构建Web组件下一篇Apache Ignite 在Linux系统下的DEB/RPM包安装指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考