跳到主要内容
约 2 分钟2 张卡

数组

数组按下标组织同类元素，适合随机访问和顺序扫描。本文负责下标、有效长度、插入删除和扩缩容。

1. 面试核心​

先记住这几条，再读正文
  • 访问与查找。 数组按下标访问为 O(1)，因为可根据起始地址和元素大小定位；无序按值查找最坏为 O(n)，需要逐项比较。
  • 保序删除。 数组保序删除要前移后续元素，最坏移动 n−1 项，时间为 O(n)。已知下标且允许乱序时，可用末项覆盖，将删除降为 O(1)。卡 · 使用边界
  • 动态扩容。 动态数组倍增扩容时，尾部追加摊销 O(1)。这是对一串操作的平均成本，触发迁移的单次追加仍需 O(n)。卡 · 插入与扩容

2. 下标与连续槽位​

等宽槽位可用 起始地址 + 下标 × 槽位大小 定位。访问第 100 项无需经过前 99 项。连续访问槽位有利于 CPU 缓存利用。引用所指对象的布局则由运行时管理。

本文采用连续槽位的数组实现模型。Java 语言规范定义下标与类型，未规定物理布局。

int[] values = {4, 7, 9};
values[1] = 8;
System.out.println(values[1]); // 8

写入替换了下标 1 的值，长度仍为 3。Java 下标从 0 开始，下标 3 会越界。动态容器另用 size 记录有效元素数。业务值 0 也可以是有效元素。

3. 插入与扩容​

卡 · 倍增扩容为何摊销 O(1)，缩容阈值为何要留间隔？

在 [4,8,9] 的下标 1 插入 6，需要将 8、9 后移。容量已满时，还需分配更大的数组。保序删除则将后缀前移。

容量每次翻倍时，复制次数构成等比数列。追加 n 项的累计复制量为 O(n)。因此，尾部追加摊销 O(1)，单次扩容为 O(n)。每次只扩一格会累计复制 O(n²) 项。

3.1 扩缩容阈值​

扩容与缩容应留出间隔。例如满时翻倍，使用量降到四分之一时减半。缩容后数组仍有一半空位。

若使用量刚到一半就减半，数组会立即变满。交替插入和删除便会反复复制。预留阈值间隔能让两次迁移间积累足够多的操作。

4. 使用边界​

卡 · 数组保序删除为何是 O(n)，何时可降到 O(1)？

数组适合固定大小表格和批量扫描。中间修改的成本包括定位与移动。链表定位插入点最坏也需 O(n)。

允许改变顺序时，可用末尾元素覆盖待删位置。已知下标的删除因此可达 O(1)。随后减少 size，并清空多余的引用槽位。保留下来的外部下标也需同步更新。

5 · 面试题卡片​

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。
逐张翻看 2 张 →
使用边界
数组保序删除为何是 O(n)，何时可降到 O(1)？
本站自测
考察 1 点 · 相关 §4未标记
插入与扩容
倍增扩容为何摊销 O(1)，缩容阈值为何要留间隔？
本站自测
考察 1 点 · 相关 §3未标记
未标记的卡读完后明天进入复习；已标记的按状态安排
本页题目与参考回答

5.1 数组保序删除为何是 O(n)，何时可降到 O(1)？​

考察重点：顺序、定位与移动的成本。

相关内容：使用边界。

参考回答

保序删除最坏需前移 n−1 项，时间为 O(n)。

已知下标且允许乱序时，可用末项覆盖。再减少有效长度，操作为 O(1)。若需先按值查找，总时间仍最坏为 O(n)。

5.2 倍增扩容为何摊销 O(1)，缩容阈值为何要留间隔？​

考察重点：累计复制量与迁移频率。

相关内容：插入与扩容。

参考回答

倍增时，n 次追加的累计复制量为 O(n)。

均摊到每次追加就是 O(1)。缩容阈值留出间隔，可避免交替增删触发反复迁移。摊销结论约束操作序列，单次迁移仍需 O(n)。

6. 参考资料​

本页
有对应面试题卡片