{{ selected_gold.title }}

  • ¥ {{ selected_gold.original_price }}
  • ¥ {{ selected_gold.price }}
点击阅读
  • {{ selected_gold.number_of_order }} 人订阅
    • {{ selected_gold.total_likers_count }}
    由 {{ selected_gold.creator_name }} 编辑

    {{ title }}

    请登录购买（{{ selected_gold.price }}元），即可解锁剩余教程
    点击购买
    • Air
    • 2020年12月19日

    数组

    数组是一堆元素的集合，它没有任何规律，一般通过下标来存取，因此，它也有Hash的功能，其中的下标就是Hash的key。常见的数组有一维数组、二维数组等，二维数组有点类似于矩阵，需要通过行列下标来获取二维数组里的元素。数组非常适合于固定数量的元素，如果涉及到变化的元素，那么链表会是一个不错的选择！

    本文将通过以下几方面来介绍数组：

    • 定义
    • 实现和操作
    • 空间复杂度和时间复杂度

    定义

    In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.[1][2][3] The simplest type of data structure is a linear array, also called one-dimensional array.

    由以上定义可知，数组是有一堆元素组成，每一个元素可以通过一个或多个下标来存取。最简单的数组是一维数组，它的下标编号从0开始，如下图所示：

    元素2对应的下标是0，7对应的下标是1，以此类推！通过下标0，可以存取元素2，同理，通过下标2，则可以存取元素1。通过下标来存取某个元素的特性常常被称为随机存取，而为了让数组具备随机存取特性，这就要求存储元素的内容必须是连续的，这就引发了以下几个问题：

    1. 如果Logical Size大于Capacity，那么需要重新分配一块更大的连续存储空间，并将之前的所有元素拷贝到新的存储空间，这就导致拷贝操作会受到元素个数的影响
    2. 无法高效地在已经存在的元素之间插入新的元素。要想在已存在的元素之间插入新元素，需要将插入位置之后的所有元素向后移动，这也涉及到了拷贝元素的操作，会受到需要拷贝元素的数量影响

    因此，与数组相关的操作有：

    1. index通过下标存取元素
    2. append向数组中追加元素
    3. pop向数组中移除最新追加的元素

    实现和操作

    class Array:
    def __init__(self, capacity=10):
        self.logical_size = 0
        self.capacity = capacity
        self.data = [0] * capacity

    def append(self, val):
        if self.logical_size == self.capacity:
            alloc_capacity = 2 * len(self.data)
            self.data = self.data + [0] * alloc_capacity
            self.capacity += alloc_capacity
        self.data[self.logical_size] = val
        self.logical_size += 1

    def pop(self):
        if self.logical_size == 0:
            return None
        else:
            res = self.data[self.logical_size - 1]
            self.logical_size -= 1
            return res

    def index(self, i):
        if i < self.logical_size:
            return self.data[i]
        else:
            return None

    def print(self):
        print(self.data[:self.logical_size])

    以下是如何使用上面定义的数组：

    one_dim_arr = Array()
one_dim_arr.append(10)
one_dim_arr.append(5)
one_dim_arr.append(106)
one_dim_arr.append(69)
one_dim_arr.pop()
one_dim_arr.append(12)

one_dim_arr.print()

    最终的输出结果如下所示：

    [10, 5, 106, 12]

    空间复杂度和时间复杂度

    接下来，让我们看看以上定义的每一种方法，它们的空间复杂度和时间复杂度是多少。

    • index通过下标存取元素，它的空间复杂度是O(1)，时间复杂度是O(1)
    • append向数组中追加元素，如果数组里依然有多余的空间，那么它的空间复杂度是O(1)，时间复杂度是O(1)，如果数组里没有多余的空间，那么它的空间复杂度是O(n)，时间复杂度是O(n)
    • pop向数组中移除最新追加的元素，它的空间复杂度是O(1)，时间复杂度是O(1)

    数组有它致命的弱点，比如调用append时，很有可能会发生拷贝行为，除此之外，在数组中间添加元素也会引起拷贝行为，而这些拷贝行为又是非常耗时的。如果你不想让这些拷贝行为发生，那么链表会是一个不错的选择！