实现动态数组

假设理解 Big O 表示法。 JavaScript 中有示例。资料参考 Gayle Laakmann McDowell 的《Cracking the Coding Interview》

介绍

在 JavaScript 或 Python 等某些语言中，数组会自动调整大小，这意味着数组会随着您追加项目而增长。在 Java 等其他语言中，数组是固定长度的，这意味着数组的大小是在初始化数组时定义的。这些自动增长的数组称为动态数组。

了解动态数组

在 Java 中，ArrayList 是一种类似数组的数据结构，它提供动态调整大小的同时仍然提供 $O(1)$O(1) 使用权。当数组已满时，数组的大小会加倍。每次加倍需要 $O(n)$O(n) 时间，但发生的情况很少，因此其摊销插入时间仍然是 $O(1)$O(1) .

在不同的编程语言中，该数据结构的名称及其调整大小因子（Java 中为 2）各不相同。调整大小因子决定数组大小将调整多大。

为什么是摊销插入时间 $O(1)$O(1) ？

调整大小时，假设调整大小因子为 2，我们可以观察到通过将前一个数组加倍（即 N 的一半），我们增加到大小为 N 的数组。此外，我们还需要复制 $N\mathrm{/}2$N/2 元素添加到这个新数组。

如果我们将从最终容量增加到第一次容量增加复制的元素数量相加： $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+\mathrm{.}\mathrm{.}\mathrm{.}+2+1$ 2n​+4n​+8n​+16n​+...+2+1 其总和略小于 N。因此，插入 N 个元素大约需要 $O(n)$O(n) 总共工作。每次插入都是 $O(1)$O(1) 平均而言，即使某些插入需要 $O(n)$O(n) 最坏情况下的时间。

核心概念和大O复杂性

JavaScript 中的动态数组通常有几个核心方法，每个方法都有不同的时间复杂度：

get(i)：此方法检索索引 i 处的元素。

• 复杂性： $O(1)$O(1)

set(i, n)：该方法将索引 i 处的元素设置为 n。

• 复杂性： $O(1)$O(1)

pushback(n)：该方法将元素 n 添加到数组末尾。

• 复杂性： $O(1)$O(1) 摊销，但是 $O(n)$O(n) 当调整大小时

popback()：该方法删除数组的最后一个元素。

• 复杂性： $O(1)$O(1)

resize()：该方法将数组的容量加倍，并将所有元素复制到新数组。

• 复杂性： $O(n)$O(n)

getSize()：该方法返回数组中元素的数量。

• 复杂性： $O(1)$O(1)
• 注意：我们可以通过使用大小变量来跟踪数组中已填充槽的数量来实现这种复杂性。

getCapacity()：该方法返回数组的当前容量。

• 复杂性： $O(1)$O(1)

JavaScript 中的实现

class DynamicArray {
    // size is # of filled slots while capacity is total slots in array
    constructor(capacity) {
        this.capacity = capacity;
        this.arr = new Array(this.capacity);
        this.size = 0;
    }

    // O(1)
    get(i) {
        if (i < 0 || i >= this.size) return undefined;
        return this.arr[i];
    }

    // O(1)
    set(i, n) {
        if (i < 0 || i >= this.size) return undefined;
        this.arr[i] = n;
    }

    // O(1) amortized 
    pushback(n) {
        if (this.size === this.capacity) {
            this.resize();
        }
        this.arr[this.size] = n;
        this.size++;
    }

    // O(1) 
    popback() {
        if (this.size === 0) return undefined;
        this.size--;
        let temp = this.arr[this.size];
        this.arr[this.size] = undefined;
        return temp;

    }

    // O(n)
    resize() {
        this.capacity *= 2;
        let newArr = new Array(this.capacity);
        for (let i = 0; i < this.size; i++) {
            newArr[i] = this.arr[i];
        }
        this.arr = newArr;
    }

    // O(1)
    getSize() {
        return this.size;
    }

    // O(1) 
    getCapacity() {
        return this.capacity;
    }
}

结论

动态数组是一种强大的数据结构，它结合了可调整存储大小的灵活性和恒定时间访问的效率。希望这有帮助！

以上是实现动态数组的详细内容。更多信息请关注PHP中文网其他相关文章！