LeetCode 补充题 142. 实现动态整数数组

约 5 分钟
文章信息 3 个分类 2 个标签
分类
补充题 中等 滴滴
标签
数组 设计

题目描述

不用内置动态列表，实现一个支持以下操作的整数容器：

  • size：返回容器中的元素个数。
  • get：读取指定下标的元素。
  • set：修改指定下标的元素。
  • add：在尾部追加元素。
  • insert：按下标插入元素，允许下标等于 size。
  • remove：按下标删除元素并返回被删除的值。

下标越界时抛出异常或 panic。

示例 1：

输入： 操作 = [add(2), add(4), insert(1,3), remove(0), get(0), size()]
输出： 查询及删除结果 = [2,3,2]
解释： 插入后容器为 [2,3,4]；删除下标 0 返回 2，容器变为 [3,4]，首元素为 3，长度为 2。

提示：

  • get、set、remove 的下标范围为 0…size-1，insert 的范围为 0…size。
  • 越界抛异常或 panic。
  • add 在尾部追加。

题意分析

动态数组要区分逻辑元素数与底层容量：读写下标只允许进入有效区间，而追加可以利用预留空间。容量不足时才整体复制，避免每追加一项就重新分配一次。

解法：几何扩容与原生数组搬移

核心思路

[!blue]

有效元素始终位于 [0,size)。get、set、remove 要求 index < size，insert 允许 index == size，因此插入的边界检查必须单独处理。

插入前若容量不足，将容量扩为两倍，零容量则从 1 开始。历次扩容复制量形成 1 + 2 + 4 + … 的几何级数，总量与累计追加次数同阶，所以尾部追加是均摊常数时间，单次扩容仍是线性时间。

在中间插入需要将后缀右移，删除则先保存返回值，再将后缀左移填洞。代码使用支持重叠区间的 arraycopy 或 copy，避免覆盖尚未搬移的值。删除只缩短有效长度、不缩容量，故存储量取决于历史峰值。

解题步骤

  1. 区分有效长度 size 与底层容量，读取和覆盖先检查有效下标。
  2. 容量不足时加倍并复制，尾部追加不需要移动现有元素。
  3. 中间插入先右移后缀，删除则左移填补空位。
  4. 更新 size；当前实现删除后保留容量。

代码实现

class IntArray {
    private int[] values = new int[1];
    private int size;

    public int size() {
        return size;
    }

    private void check(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }

    public int get(int index) {
        check(index);

        return values[index];
    }

    public void set(int index, int value) {
        check(index);
        values[index] = value;
    }

    public void add(int value) {
        insert(size, value);
    }

    public void insert(int index, int value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        if (size == values.length) {
            values = Arrays.copyOf(values, Math.multiplyExact(values.length, 2));
        }

        System.arraycopy(values, index, values, index + 1, size - index);
        values[index] = value;
        size++;
    }

    public int remove(int index) {
        check(index);
        int old = values[index];

        System.arraycopy(values, index + 1, values, index, size - index - 1);
        size--;

        return old;
    }
}

type IntArray struct {
    values []int
    size   int
}

func (a *IntArray) Size() int {
    return a.size
}

func (a *IntArray) check(index int) {
    if index < 0 || index >= a.size {
        panic("index out of bounds")
    }
}

func (a *IntArray) Get(index int) int {
    a.check(index)
    return a.values[index]
}

func (a *IntArray) Set(index, value int) {
    a.check(index)
    a.values[index] = value
}

func (a *IntArray) Add(value int) {
    a.Insert(a.size, value)
}

func (a *IntArray) Insert(index, value int) {
    if index < 0 || index > a.size {
        panic("index out of bounds")
    }
    if a.size == len(a.values) {
        capacity := max(1, len(a.values)*2)
        if capacity < a.size {
            panic("capacity overflow")
        }
        next := make([]int, capacity)
        copy(next, a.values)
        a.values = next
    }
    copy(a.values[index+1:a.size+1], a.values[index:a.size])
    a.values[index] = value
    a.size++
}

func (a *IntArray) Remove(index int) int {
    a.check(index)
    old := a.values[index]
    copy(a.values[index:a.size-1], a.values[index+1:a.size])
    a.size--
    return old
}

复杂度分析

  • 时间复杂度：随机读写 $O(1)$，尾部追加均摊 $O(1)$、单次扩容最坏 $O(n)$，中间插入删除 $O(n)$，这里 n 是当前元素数。
  • 空间复杂度：存储空间为 $O(C)$，C 是保留的数组容量；删除后不缩容，因此容量由历史最大长度决定，不能按删除后的当前 size 估计。

关键点总结

[!green]

几何扩容摊薄的是累计复制成本，不会把任意一次扩容变成最坏常数时间；容量也不等于当前元素数。

易错点总结

[!yellow]

扩容只在容量不足时触发；插入与删除的合法下标上界不同。

相似题目

题目 难度 关联与区别
补充题 121. 用数组实现定长栈 中等 固定栈容量不增长，动态数组追加则要区分均摊时间与扩容当次复制。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/98253172
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！