前置知识: 算法与数据结构

数组与动态数组

7 minBeginner2026/6/14

数组的连续内存模型、随机访问与插入删除复杂度分析，动态数组的扩容机制与均摊复杂度。

1. 数组概述

1.1 什么是数组

数组（Array）是最基础的数据结构之一，它将相同类型的元素存储在一段连续的内存空间中，通过索引（下标）直接访问任意元素。这种连续存储的特性赋予了数组极高的随机访问效率，同时也带来了插入和删除操作的高开销。

1.2 内存模型

内存地址:  1000  1004  1008  1012  1016
索引:       0     1     2     3     4
值:        10    20    30    40    50
           ┌────┬────┬────┬────┬────┐
           │ 10 │ 20 │ 30 │ 40 │ 50 │
           └────┴────┴────┴────┴────┘

给定基地址 base 和元素大小 size，第 i 个元素的地址为：

address(i) = base + i × size

这个公式是 O(1) 的计算，正是数组随机访问高效的根本原因。

1.3 核心特性

特性说明
内存布局连续
随机访问O(1)
头部插入O(n)（需移动所有元素）
尾部插入O(1)（有空间时）
任意位置插入O(n)（平均需移动 n/2 个元素）
任意位置删除O(n)（平均需移动 n/2 个元素）
按值查找O(n)（无序）/ O(log n)（有序，二分）
缓存局部性极好（CPU 缓存行预取）

2. 数组的基本操作

2.1 静态数组的创建与访问

// Java
int[] arr = new int[5];           // 创建长度为5的数组，默认值为0
int[] arr2 = {10, 20, 30, 40, 50}; // 直接初始化
int val = arr2[2];                 // 随机访问，O(1)
arr2[3] = 100;                     // 按索引修改，O(1)
// C++
int arr[5];                        // 栈上静态数组
int* arr2 = new int[5];            // 堆上动态分配
std::array<int, 5> arr3 = {1,2,3,4,5}; // C++11 固定大小数组
int val = arr3[2];                 // O(1)
# Python 列表本质是动态数组
arr = [10, 20, 30, 40, 50]
val = arr[2]                       # O(1)
arr[3] = 100                       # O(1)

2.2 插入操作

在索引 i 处插入元素，需要将 i 及之后的元素全部后移一位：

// Java：在索引 pos 处插入元素 val
public static void insert(int[] arr, int size, int pos, int val) {
    if (pos < 0 || pos > size) {
        throw new IndexOutOfBoundsException();
    }
    // 从后向前移动元素
    for (int i = size; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    arr[pos] = val;
}
# Python
def insert(arr, pos, val):
    # 从后向前移动
    arr.append(0)  # 扩展一位
    for i in range(len(arr) - 1, pos, -1):
        arr[i] = arr[i - 1]
    arr[pos] = val

时间复杂度分析：

  • 最好情况：在末尾插入，O(1)
  • 最坏情况：在开头插入，O(n)
  • 平均情况：O(n)

2.3 删除操作

删除索引 i 处的元素，需要将 i 之后的元素全部前移一位：

// Java：删除索引 pos 处的元素
public static int delete(int[] arr, int size, int pos) {
    if (pos < 0 || pos >= size) {
        throw new IndexOutOfBoundsException();
    }
    int removed = arr[pos];
    // 从前向后移动元素
    for (int i = pos; i < size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    arr[size - 1] = 0; // 可选：清空末尾
    return removed;
}
// C++：删除索引 pos 处的元素
int remove(std::vector<int>& arr, int pos) {
    int removed = arr[pos];
    for (int i = pos; i < (int)arr.size() - 1; i++) {
        arr[i] = arr[i + 1];
    }
    arr.pop_back();
    return removed;
}

时间复杂度：与插入相同，平均 O(n)。

3. 动态数组（Dynamic Array）

3.1 为什么需要动态数组

静态数组在创建时必须指定大小，且之后无法改变。当元素数量超过容量时，就无法继续添加。动态数组（Dynamic Array）解决了这个问题——它在内部维护一个容量可变的底层数组，当空间不足时自动扩容。

各语言中的动态数组实现：

语言动态数组类
JavaArrayList<E>
C++std::vector<T>
Pythonlist
JavaScriptArray
Goslice
RustVec<T>

3.2 扩容机制

当元素数量达到当前容量时，动态数组会执行以下步骤：

  1. 分配一块更大的新内存（通常是原来的 1.5 倍或 2 倍）
  2. 将旧数组的所有元素复制到新数组
  3. 释放旧数组内存
  4. 后续操作使用新数组
扩容前 (capacity=4, size=4):
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘

扩容后 (capacity=8, size=5):
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │    │    │    │
└────┴────┴────┴────┴────┴────┴────┴────┘

3.3 各语言扩容策略

// Java ArrayList (OpenJDK)：1.5 倍扩容
private int newCapacity(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
    if (newCapacity - minCapacity <= 0) {
        newCapacity = minCapacity;
    }
    return newCapacity;
}
// C++ std::vector (GCC libstdc++)：2 倍扩容
// 关键代码在 _M_fill_insert 中：
size_type __len = size() + std::max(size(), __n); // 2倍或按需
# CPython list：约 1.125 倍扩容（增长公式：(newsize >> 3) + (newsize < 9 ? 3 : 6)）
# 实际增长较慢，但每次追加的均摊成本仍然 O(1)

3.4 手动实现动态数组

// Java 手动实现动态数组
public class MyArrayList<E> {
    private Object[] data;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList() {
        data = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    public int size() { return size; }

    public boolean isEmpty() { return size == 0; }

    // 尾部追加
    public void add(E element) {
        ensureCapacity(size + 1);
        data[size++] = element;
    }

    // 指定位置插入
    public void add(int index, E element) {
        checkIndexForAdd(index);
        ensureCapacity(size + 1);
        System.arraycopy(data, index, data, index + 1, size - index);
        data[index] = element;
        size++;
    }

    // 按索引删除
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        checkIndex(index);
        E oldValue = (E) data[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(data, index + 1, data, index, numMoved);
        }
        data[--size] = null; // 帮助 GC
        return oldValue;
    }

    // 按索引访问
    @SuppressWarnings("unchecked")
    public E get(int index) {
        checkIndex(index);
        return (E) data[index];
    }

    // 扩容核心逻辑
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > data.length) {
            int newCapacity = data.length + (data.length >> 1); // 1.5倍
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            Object[] newData = new Object[newCapacity];
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index);
    }

    private void checkIndexForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: " + index);
    }
}
# Python 手动实现动态数组
class MyList:
    def __init__(self, capacity=10):
        self._data = [None] * capacity
        self._size = 0
        self._capacity = capacity

    def __len__(self):
        return self._size

    def __getitem__(self, index):
        if index < 0 or index >= self._size:
            raise IndexError("Index out of range")
        return self._data[index]

    def __setitem__(self, index, value):
        if index < 0 or index >= self._size:
            raise IndexError("Index out of range")
        self._data[index] = value

    def append(self, value):
        self._ensure_capacity(self._size + 1)
        self._data[self._size] = value
        self._size += 1

    def insert(self, index, value):
        if index < 0 or index > self._size:
            raise IndexError("Index out of range")
        self._ensure_capacity(self._size + 1)
        # 从后向前移动
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]
        self._data[index] = value
        self._size += 1

    def pop(self, index=None):
        if index is None:
            index = self._size - 1
        if index < 0 or index >= self._size:
            raise IndexError("Index out of range")
        removed = self._data[index]
        # 从前向后移动
        for i in range(index, self._size - 1):
            self._data[i] = self._data[i + 1]
        self._data[self._size - 1] = None
        self._size -= 1
        return removed

    def _ensure_capacity(self, min_capacity):
        if min_capacity > self._capacity:
            new_capacity = max(self._capacity * 2, min_capacity)
            new_data = [None] * new_capacity
            for i in range(self._size):
                new_data[i] = self._data[i]
            self._data = new_data
            self._capacity = new_capacity

4. 均摊复杂度分析

4.1 均摊分析（Amortized Analysis）

均摊分析是一种评估一系列操作平均代价的方法。对于动态数组的 append 操作：

  • 大多数时候：直接在末尾写入，O(1)
  • 偶尔：触发扩容，需要复制 n 个元素，O(n)

关键问题：如何将扩容的 O(n) 代价均摊到每次操作上？

4.2 聚合分析法

假设从空数组开始，连续执行 n 次 append：

操作次数扩容发生扩容代价写入代价总代价
1否011
……………
n+1是n1n+1
……………

以 2 倍扩容为例，扩容发生在第 1, 2, 4, 8, 16, … 次插入时：

总代价 = n（每次写入1）+ 1 + 2 + 4 + ... + n/2 + n
       = n + (2n - 1)
       ≈ 3n

因此 n 次 append 的总代价为 O(n)，均摊每次 O(1)。

4.3 势能分析法

定义势函数 Φ(D) = 2 × size - capacity（2倍扩容策略下）：

  • 普通插入：实际代价 1，势能变化 +2，均摊代价 = 1 + 2 = 3 = O(1)
  • 扩容插入：实际代价 n+1（复制n个+写入1个），势能变化 = 2n - 2(n-1) = 2-n，均摊代价 = (n+1) + (2-n) = 3 = O(1)

两种方法都证明了 动态数组 append 的均摊时间复杂度为 O(1)。

4.4 缩容机制

当元素大量删除时，为避免内存浪费，动态数组会进行缩容：

// 缩容策略：当 size < capacity / 4 时，缩容为 capacity / 2
// 注意：不使用 capacity / 2 作为阈值，避免在临界点反复扩容缩容（抖动）
private void shrink() {
    if (size < data.length / 4 && data.length > DEFAULT_CAPACITY) {
        int newCapacity = Math.max(data.length / 2, DEFAULT_CAPACITY);
        Object[] newData = new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }
}

阈值选择：使用 capacity/4 而非 capacity/2 作为缩容阈值，是为了避免在 capacity/2 附近反复扩容和缩容导致的复杂度抖动。

5. 多维数组

5.1 二维数组的内存布局

二维数组有两种存储方式：

行优先（Row-major）——C/C++/Java 等大多数语言：

a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2]

列优先（Column-major）——Fortran/MATLAB 等：

a[0][0] a[1][0] a[2][0] a[0][1] a[1][1] a[2][1]

5.2 地址计算

对于 m × n 的二维数组（行优先），元素 a[i][j] 的地址：

address(a[i][j]) = base + (i × n + j) × size
// C++：用一维数组模拟二维数组（缓存友好）
int m = 3, n = 4;
int* flat = new int[m * n];
// 访问 [i][j]
flat[i * n + j] = 42;

6. 常见面试题型

6.1 双指针技巧

// 原地删除有序数组中的重复元素（LeetCode 26）
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
        }
    }
    return slow + 1;
}

6.2 滑动窗口

# 长度最小的子数组（LeetCode 209）
def minSubArrayLen(target, nums):
    left = 0
    total = 0
    min_len = float('inf')
    for right in range(len(nums)):
        total += nums[right]
        while total >= target:
            min_len = min(min_len, right - left + 1)
            total -= nums[left]
            left += 1
    return min_len if min_len != float('inf') else 0

6.3 前缀和

// 区域和检索（LeetCode 303）
class NumArray {
    private int[] prefix;

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

6.4 差分数组

# 区间加法（LeetCode 370 / 1109）
def getModifiedArray(length, updates):
    diff = [0] * length
    for start, end, inc in updates:
        diff[start] += inc
        if end + 1 < length:
            diff[end + 1] -= inc
    # 还原
    for i in range(1, length):
        diff[i] += diff[i - 1]
    return diff

7. 数组 vs 链表选择指南

场景推荐结构原因
频繁随机访问数组O(1) 随机访问
频繁头部/中间插入删除链表数组需 O(n) 移动元素
元素数量已知且不变数组无额外指针开销
元素数量变化大动态数组自动扩容，均摊 O(1) 追加
需要缓存友好数组连续内存，CPU 预取高效
需要频繁在任意位置增删链表已知前驱时 O(1) 插入/删除
多线程安全（读写分离场景）链表修改不影响其他节点的内存位置

8. 性能优化实践

8.1 预分配容量

// 不好的做法：频繁触发扩容
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    list.add(i); // 多次扩容
}

// 好的做法：预分配容量
List<Integer> list = new ArrayList<>(100000);
for (int i = 0; i < 100000; i++) {
    list.add(i); // 无扩容
}

8.2 批量插入优于逐个插入

// C++：reserve + 批量操作
std::vector<int> vec;
vec.reserve(10000);  // 一次性分配
for (int i = 0; i < 10000; i++) {
    vec.push_back(i); // 不会扩容
}

8.3 避免在中间频繁插入

# 不好的做法：在列表头部反复插入
result = []
for item in data:
    result.insert(0, item)  # 每次 O(n)

# 好的做法：尾部追加后反转
result = []
for item in data:
    result.append(item)  # 均摊 O(1)
result.reverse()  # O(n)

9. 总结

操作静态数组动态数组（均摊）
随机访问O(1)O(1)
尾部插入O(1)O(1)
头部插入O(n)O(n)
任意位置插入O(n)O(n)
任意位置删除O(n)O(n)
按值查找（无序）O(n)O(n)
按值查找（有序）O(log n)O(log n)
扩容不支持O(n)，均摊 O(1)

数组是最基础的数据结构，理解其连续内存模型和缓存局部性特征，对于后续学习排序、查找、动态规划等算法至关重要。动态数组的均摊分析思想也是算法复杂度分析的重要方法论。