数据结构学习笔记 - 02 数组

介绍

• 数组最大的优点是可以快速查询，如 scores[2]；
• 数组最好应用于 “索引有语意” 的情况；

复杂度

操作	复杂度
增	O(n)
删	O(n)
改	已知索引 O(1) 未知索引 O(n)
查	已知索引 O(1) 未知索引 O(n)
addLast(e)	O(1)
addFirst(e)	O(n)
add(index, e)	O(n)
removeLast(e)	O(1)
removeFirst(e)	O(n)
remove(index, e)	O(n)
resize	O(1) （均摊复杂度）

静态数组

数组简单来讲就是将一组数据码成一排进行存放。内存中，会开辟一个连续的区间存放数组。一旦创建，数组的容量是固定的。

不同语言对数组的实现会略有不同：

语言	实现	类型	元素	可变
Java	E[]（E 表示类型，如 int）	引用类型	指定类型	容量不可变，元素可变
Objective-C	NSArray	引用类型	对象类型	容量不可变，元素可变
Swift	Array	值类型	指定类型	容量和元素均不可变

首先，三种语言的数组容量都是不可变的，这也是静态数组的特点，空间一旦开辟，就固定了；其次，对于元素的类型，Objective-C 是只要是对象即可，因此对元素类型的限制较小，而其他两种语言要求元素必须为指定的类型；最后，Swift 的数组使用值类型，而另外两种采用引用类型，这也使得 Swift 数组创建后，元素就无法做更改了。

动态数组的实现

动态数组使用静态数组实现，它必须要有的几个成员变量：

• E[] data：使用一个静态数组作为容器来存放元素；
• int capacity: 当前数组的容量，可以使用 data.length 表示；
• int size：当前数组存放元素的个数；

使用 Java 实现：

public class Array<E> {

    // 使用一个静态数组来存放元素，也就是当前数组的容量。
    private E[] data;
    // 数组中存放元素的个数。
    private int size;

    /**
     * 构造函数。
     * 
     * @param capacity 数组初始容量。
     */
    @SuppressWarnings("unchecked")
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 无需传入数组容量的构造函数。默认初始容量为 10。
     */
    public Array() {
        this(10);
    }

    /**
     * 通过一个静态数组构造动态数组。
     * 如：Array<Integer> arr = new Array<>(new Integer[]{3, 1, 2});
     * 
     * @param arr 静态数组。
     */
    @SuppressWarnings("unchecked")
    public Array(E[] arr) {
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        size = arr.length;
    }

    /**
     * 获取数组的容量。
     * 
     * @return 数组的容量。
     */
    public int getCapacity() {
        return data.length;
    }

    /**
     * 获取数组中元素的个数。
     * 
     * @return 数组中元素的个数。
     */
    public int getSize() {
        return size;
    }

    /**
     * 数组是否为空。
     * 
     * @return 数组是否为空。
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在指定索引添加一个元素。
     * 时间复杂度最大为 O(n)，最小为 O(1)。总体计算应该算出各个可能性的期望复杂度，最终是 O(n/2)，由于常数忽略，所以还是 O(n)。
     * 
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        // 索引必须合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
        }

        if (size == data.length) {
            // 修改前，如果数组已经满了，则无法添加新元素，抛出异常。
            // throw new IllegalArgumentException("Add failed. Array is full.");
            // 修改后，如果数组已经满了，则不再抛出异常，而是容量翻倍。
            resize(2 * data.length);
        }

        // 将索引后面的元素依次向后挪动一个位置，应该从最后一个元素开始挪起。
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        data[index] = e;
        size++;
    }

    /**
     * 向数组末尾添加元素。
     * 时间复杂度 O(1)，因为算法运行时间和输入数据规模无关，是一个常数，也就是和数组元素个数无关。
     * 
     * @param e 元素。
     */
    public void addLast(E e) {
        // 尾部添加一个元素可以调用 add 方法。
        add(size, e);
        // // 如果数组已经满了，则无法添加新元素，抛出异常。
        // if (size == data.length) {
        // throw new IllegalArgumentException("AddLast failed. Array is full.");
        // }
        // data[size] = e;
        // size++;
    }

    /**
     * 在数组开头插入一个元素。
     * 时间复杂度 O(n)，因为需要向后挪动 n 个元素，数组中所有内容都要向后挪动。
     * 
     * @param e 插入的元素。
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 获取某个元素。
     * 时间复杂度 O(1)。
     * 
     * @param index 索引。
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        }

        return data[index];
    }

    /**
     * 获取数组最后一个元素。
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 获取数组第一个元素。
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 修改 index 索引位置的元素为 e。
     * 时间复杂度 O(1)。这也是数组最大的优势，支持随机访问，知道索引的情况下改元素超快。
     * 
     * @param index 索引。
     * @param e     新设置的元素。
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        }

        data[index] = e;
    }

    /**
     * 查找数组中是否包含某个元素。
     * 时间复杂度 O(n)。
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找元素 e 所在的第一个索引，如果不存在该元素，则返回 -1。
     * 时间复杂度 O(n)。
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 从数组中删除指定索引的元素，并将其返回。
     * 时间复杂度 O(n)
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed. Index is Illegal.");
        }

        E ret = data[index];

        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null; // 可写可不写，写的话可以优化一点点内存。loitering objects != memory leak

        // 缩容采取 lazy 的策略，元素变为 1/4 时再进行缩容。
        // 这样的目的是防止复杂度震荡。
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return ret;
    }

    /**
     * 删除第一个元素。
     * 时间复杂度 O(n)
     * 
     * @return 删除的元素。
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 删除最后一个元素。
     * 时间复杂度 O(1)
     * 
     * @return 删除的元素。
     */
    public E removeLast() {
        return remove(size - 1);
    }

    /**
     * 如果数组包含元素 e，则删除第一个 e。
     * 
     * @param e
     */
    public void removeElement(E e) {
        int index = find(e);
        if (index != -1) {
            remove(index);
        }
    }

    /**
     * 交换数组中指定两个索引的元素
     */
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("Index is illegal.");
        }

        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    /**
     * 改变数组容量。
     * 
     * 对于该算法复杂度的分析，最合适的应该是均摊复杂度分析，而不应该使用最坏的情况。因为 resize 操作是不可能每次添加元素都触发的。
     * 由于不是每次操作都触发，则这次的耗时可以分摊到每一次操作中。
     * 使用均摊复杂度分析的复杂度是 O(1) 级别的
     * 
     * 但是，如果我们正好在扩容和缩容的边界反复交替调用 addLast 和 removeLast 的话，复杂度就一直是 O(n) 级别的，这叫做复杂度震荡。
     * 为了防止复杂度震荡，我们可以在缩容的时候采取 lazy 的策略，即元素个数到 1/2 容量时先不要锁容，而等到更小，比如 1/4 的时候再进行。
     * 
     * @param newCapacity 需要变更的容量。
     */
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {

        if (newCapacity < size) {
            throw new IllegalArgumentException("New capacity is Illegal.");
        }

        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1) {
                res.append(", ");
            }
        }
        res.append(']');
        return res.toString();
    }
}

总结：

• 对于增删操作，最好的情况是 O(1) 即增删在尾部，最差的情况是 O(n) 即增删在首位，平均还是 O(n)；
• 对于数组越界的处理，我们都选择抛出异常使程序中断，而不是采取返回空等温和的做法；
• 改变数组的 resize 操作的复杂度分析需要使用均摊复杂度分析，最终该操作的复杂度是 O(1) 级别；
• rezize 操作为避免复杂度震荡，缩容操作采用了延迟的策略；