02-数组 | FHCY-Study

type

status

date

slug

summary

1️⃣ 动态数组

特性	说明
✅ 支持动态扩容	数组满时自动扩大容量
✅ 连续内存存储	依然是顺序结构，支持随机访问
✅ 按索引访问快	与静态数组一样，访问元素
⚠️ 扩容时有性能抖动	需申请新数组并复制原数据，开销为

1.扩容策略

语言/库	扩容策略
Java	`ArrayList` 默认扩容为 1.5倍
C++	`vector` 扩容为 2倍
Python list	底层也是动态数组，增幅策略较复杂

2.时间复杂度分析

操作	时间复杂度	说明
随机访问		连续内存支持下标访问
尾部插入	平均，最坏	扩容时复制数据会耗费
中间插入/删除		后续元素需要移动
查找		需遍历数组

3.动态数组 vs 链表

特性	动态数组	链表
内存结构	连续	非连续（节点结构）
访问速度	（随机访问）	（需遍历）
插入/删除		（已定位节点）
空间利用	较好	较差（多指针开销）
缓存友好	✅ 是	❌ 否

4.动态数组的缺陷

缺陷	说明
扩容成本高峰	拷贝操作会造成性能抖动
插入删除效率低	频繁修改中间元素时性能差
扩容浪费空间	扩容后未用的容量暂时闲置

2️⃣ 二维数组（矩阵）

二维数组常见应用（算法方向）

应用场景	示例
图像处理	每个像素是一个二维坐标
地图模型	迷宫、棋盘、地形
动态规划	DP 表格 `dp[i][j]`
距离矩阵	图中任意两点间最短路径
表格存储	Excel 数据、数据库表格

1.矩阵旋转（Matrix Rotation）

矩阵旋转是指将一个二维数组（矩阵）顺时针或逆时针旋转 90°、180°、270°的变换操作，常用于图像处理、图形渲染、面试算法题中。

顺时针旋转 90°

逆时针旋转 90°

180° 旋转

对于非正方形矩阵（如 3×4），需要使用额外空间创建新矩阵：

2.矩阵搜索

Z 字型搜索（右上角开始）

给定一个 m x n 的矩阵 matrix，每行和每列都是升序排列的。判断目标值是否存在。

从右上角开始：

当前值 < target：往下移动（排除当前行）

当前值 > target：往左移动（排除当前列）

时间复杂度：

最多走 m + n 步，时间复杂度，空间复杂度。

一维二分查找

每一行从左到右递增，每行首元素大于上一行末元素。相当于一个一维升序数组。

m 行 n 列 => 总元素数：m * n 把二维视为一维数组：index => matrix[index / n][index % n]

时间复杂度：

二分查找：，空间复杂度

3.DFS（深度优先搜索）/BFS（广度优先搜索）

DFS 本质是 回溯 + 标记 的过程：

尽可能深入某个分支

如果走不通就回退到上一步（回溯）

遍历所有可能的路径或解

BFS核心思想：

使用队列存储待访问节点（FIFO）

每次从队列取出当前层节点，访问其所有未访问的相邻节点并加入队列

一层一层推进，直到满足目标条件或队列为空

4.DP 优化（动态规划优化）

动态规划（Dynamic Programming, DP） 是一种将大问题分解为子问题、保存子问题结果避免重复计算的算法思想。

优化类型	目的	代表例题
空间压缩（滚动数组）	降低空间复杂度	01背包、路径问题
状态转移降维	优化状态定义	斐波那契数、股票问题
斜对角/窗口优化	减少重复计算	最长回文子串、最大子矩阵
单调队列优化	优化区间转移效率	滑动窗口最大值、单调栈
分治 + 记忆化搜索	优化求解方式	石子合并、矩阵链乘法
数学 + 前缀和/位运算	替代 DP	子数组和为 K、异或子数组

空间压缩（滚动数组）

01背包空间优化

单调队列优化 DP

子问题重叠优化：记忆化搜索 vs 自底向上

典型题目分类及优化策略建议

类型	优化点	说明
背包问题	一维压缩、完全背包优化	倒序遍历 or 正序遍历
最长公共子序列	滚动数组、压缩空间	只需前一行数据
区间 DP	记忆化搜索 + 剪枝	如石子合并、矩阵链乘法
树型 DP	换根法、树形结构压缩	用邻接表/DFS 表达子树
状态机 DP	状态压缩、二维变一维	股票问题、游戏问题
多维/子集枚举	状态压缩 DP（位运算）	TSP、集合划分

3️⃣ 稀疏数组

稀疏数组（Sparse Array）是指在大多数元素为默认值（通常是 0 或 null）的数组中，仅少量位置存储有效数据的一种数据结构。它常用于节省空间和提高效率。

4️⃣ 位图（BitMap）

位图使用一个 bit 来表示一个整数是否存在，例如：

一个 int[] bitmap = new int[1_000_000 / 32] 的数组可以表示最多 1,000,000 个非负整数的存在情况。

每个 bit（0 或 1）代表一个元素是否“出现”或“被标记”。

5️⃣ 环形数组（队列）

环形数组（Circular Array），也叫环形队列（Circular Queue），是一种使用 数组实现队列 的经典结构，其关键特性是“头尾指针循环使用数组空间”，避免了假溢出问题。