02-一维数组封装和操作-复杂度分析

本讲为数据结构和算法系列第二讲，聚焦一维数组的封装与复杂度分析。

核心内容

• 一维数组封装思路：自定义容量与边界检查
• 增删改查操作实现
• 边界处理与异常设计
• 复杂度分析与动态扩容

// 自封装一维数组
public class MyArray {
    private int[] data;
    private int size;

    public MyArray(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
    }

    // O(1)
    public int get(int index) {
        checkIndex(index);
        return data[index];
    }

    // O(n)
    public void insert(int index, int value) {
        checkIndexForInsert(index);
        if (size == data.length) resize(data.length * 2);
        for (int i = size; i > index; i--) data[i] = data[i - 1];
        data[index] = value;
        size++;
    }

    // O(n) 扩容
    private void resize(int newCapacity) {
        int[] newData = new int[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        this.data = newData;
    }
}

复杂度分析

操作	时间复杂度
get(index)	O(1)
set(index)	O(1)
insert(index)	O(n)
delete(index)	O(n)
resize	O(n)（均摊后 O(1)）