数据结构：数组（Python）_python 数组

补充数组前置知识 

数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。

元素在数组中的位置称为该元素的索引（index）。

元素内存地址 = 数组内存地址(首元素地址) + [元素长度 * 元素索引](地址偏移量)。

索引本质上是内存地址的偏移量。

关于首个元素的索引为0可以这么理解：因为索引本质上是内存地址的偏移量，由于首个元素没有偏移量，或者可以说首个元素的内容地址偏移量为0，因此首个元素的索引为0。

在数组中访问元素是非常高效的，我们可以在O(1)时间内随机访问数组中的任意一个元素。

静态数组

「静态数组」就是一块连续的内存空间，我们可以通过索引来访问这块内存空间中的元素，这才是数组的原始形态。

静态数组的使用

 静态数组的定义方法：

严格来说，Python 没有静态数组的定义方式 

我们暂且使用列表模拟静态数组

# 定义一个大小为10的静态数组arr = [0] * 10# 使用索引赋值arr[0] = 1arr[1] = 2# 使用索引取值a = arr[0]

# 初始化数组arr: list[int] = [0] * 10nums: list[int] = [1,2,3,4,5]

静态数组本质上就是一块连续的内存空间

数组的访问

def random_access(nums: list[int]) -> int: \"\"\"随机访问元素\"\"\" # 在区间 [0, len(nums)-1] 中随机抽取一个数字 random_index = random.randint(0, len(nums) - 1) # 获取并返回随机元素 random_num = nums[random_index] return random_num

静态数组的增：

情况一：在数组的尾部追加（append）元素

# 大小为10的数组已经装了4个元素arr = [0] * 10for i in range(4): arr[i] = i# 现在想在数组末尾追加一个元素4arr[4] = 4# 再在数组末尾追加一个元素5arr[5] = 5

情况二，数组中间插入（insert）元素

# 大小为 10 的数组已经装了 4 个元素arr = [0] * 10for i in range(4): arr[i] = i# 在索引 2 的位置插入元素 666# 需要把索引 2 以及之后的元素都往后移动一位# 注意要倒着遍历数组中已有元素避免覆盖for i in range(4, 2, -1): arr[i] = arr[i - 1]# 现在第 3 个位置空出来了，可以插入新元素arr[2] = 666

# 编写一个在数组中插入元素的方法def insert_element(nums:list[int],num:int,index:int): # 首先向数组中插入元素，会导致在插入下标后的元素都向后移 # 因此需要从后向前遍历元素，是元素后移一位 for i in range(len(nums)-1 , index ,-1): nums[i] = nums[i-1] # 把所有的元素都向后移动完后，此时想要插入元素的index位置就空了出来 # 进行赋值 nums[index] = num

情况三，数组空间已满

连续内存必须一次性分配，分配完了之后就不能随意增减了。

此时要进行扩容操作：重新申请一块更大的内存空间，把原来的数据复制过去，再插入新的元素，这就是数组的「扩容」操作。

# 大小为10的数组已经装满了arr = [i for i in range(10)]# 现在想在数组的末尾追加一个新的元素10# 需要先扩容数组newArr = [0] * 20# 把原来的10个元素复制过去for i in range(10): newAarr[i] = arr[i]# 在新的大数组中追加新的元素newArr[10] = 10

# 扩容数组def extend(nums:list[int],large:int) -> int: # 先初始化一个长度为扩充后的数组 res = [0] * (len(nums) + large) for i in range(len(nums)): # 将原数组进行复制 res[i] = nums[i] # 返回新数组 return res

静态数组的删:

情况一，删除末尾元素

直接把末尾元素标记为一个特殊值(-1)代表已删除就行了

# 大小为10的数组已经装了5个元素arr = [0] * 10for i in range(5): arr[i] = i# 删除末尾元素，用-1来代表元素已经删除arr[4] = -1

情况二，删除中间元素

# 编写一个删除数组中索引i处元素的方法def remove(nums:list[int],index:int): # 删除某处的元素其实就是让后面的元素覆盖前面的元素 # 经过覆盖后，索引i处后面的元素相当于都往前移动了1格 for i in range(index, len(nums)-1): nums[i] = nums[i+1]

# 大小为10的数组已经装了5个元素arr = [0] * 10for i in range(5): arr[i] = i# 删除arr[1]# 需要把arr[1]之后的元素都往前移动一位# 注意要正着遍历数组中已有元素避免覆盖for i in range(1,4): arr[i] = arr[i+1]# 最后一个元素标记为-1，代表已删除arr[4] = -1

数组插入与删除的特点 

• 时间复杂度高：数组的插入和删除的平均时间复杂度均为 O(n) ，其中 n 为数组长度。
• 丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。
• 内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做会造成部分内存空间浪费。

查找元素 

在数组中查找指定元素需要遍历数组，每轮遍历都会进行判断，查看元素值是否匹配，若匹配则输出对应索引。

因为数组是线性数据结构，所以上述查找操作被称为“线性查找”。

# 查找元素def find(nums:list[int],target:int) -> int: for i in range(len(nums)): if nums[i] == target: return i return -1

动态数组 

「动态数组」是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等等方法，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。

动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装，让我们使用起来更方便而已。

# 创建动态数组# 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容量arr = []for i in range(10): # 在末尾追加元素 时间复杂度为O(1) arr.append(i)# 在中间插入元素 时间复杂度为O(N)# 在索引2的位置插入元素666arr.insert(2, 666)# 在头部插入元素 时间复杂度为O(1)arr.insert(0, -1)# 删除末尾元素 时间复杂度O(1)arr.pop()# 删除中间元素 时间复杂度O(N)# 删除索引为2的元素arr.pop(2)# 根据索引查询元素 时间复杂度O(1)a = arr[0]# 根据索引修改元素，时间复杂度 O(1)arr[0] = 100# 根据元素值查找索引，时间复杂度 O(N)index = arr.index(666)

 动态数组代码实现

class MyArrayList: # 默认初始容量 INIT_CAP = 1 def __init__(self, init_capacity=None): self.data = [None] * (init_capacity if init_capacity is not None else self.__class__.INIT_CAP) self.size = 0 # 增 def add_last(self, e): cap = len(self.data) # 看 data 数组容量够不够 if self.size == cap: self._resize(2 * cap) # 在尾部插入元素 self.data[self.size] = e self.size += 1 def add(self, index, e): # 检查索引越界 self._check_position_index(index) cap = len(self.data) # 看 data 数组容量够不够 if self.size == cap: self._resize(2 * cap) # 搬移数据 data[index..] -> data[index+1..] # 给新元素腾出位置 for i in range(self.size-1, index-1, -1): self.data[i+1] = self.data[i] # 插入新元素 self.data[index] = e self.size += 1 def add_first(self, e): self.add(0, e) # 删 def remove_last(self): if self.size == 0: raise Exception(\"NoSuchElementException\") cap = len(self.data) # 可以缩容，节约空间 if self.size == cap // 4: self._resize(cap // 2) deleted_val = self.data[self.size - 1] # 删除最后一个元素 self.data[self.size - 1] = None self.size -= 1 return deleted_val def remove(self, index): # 检查索引越界 self._check_element_index(index) cap = len(self.data) # 可以缩容，节约空间 if self.size == cap // 4: self._resize(cap // 2) deleted_val = self.data[index] # 搬移数据 data[index+1..] -> data[index..] for i in range(index + 1, self.size): self.data[i - 1] = self.data[i] self.data[self.size - 1] = None self.size -= 1 return deleted_val def remove_first(self): return self.remove(0) # 查 def get(self, index): # 检查索引越界 self._check_element_index(index) return self.data[index] # 改 def set(self, index, element): # 检查索引越界 self._check_element_index(index) # 修改数据 old_val = self.data[index] self.data[index] = element return old_val # 工具方法 def get_size(self): return self.size def is_empty(self): return self.size == 0 # 将 data 的容量改为 newCap def _resize(self, new_cap): temp = [None] * new_cap for i in range(self.size): temp[i] = self.data[i] self.data = temp def _is_element_index(self, index): return 0 <= index < self.size def _is_position_index(self, index): return 0 <= index <= self.size def _check_element_index(self, index): if not self._is_element_index(index): raise IndexError(f\"Index: {index}, Size: {self.size}\") def _check_position_index(self, index): if not self._is_position_index(index): raise IndexError(f\"Index: {index}, Size: {self.size}\") def display(self): print(f\"size = {self.size}, cap = {len(self.data)}\") print(self.data)# Usage exampleif __name__ == \"__main__\": arr = MyArrayList(init_capacity=3) # 添加 5 个元素 for i in range(1, 6): arr.add_last(i) arr.remove(3) arr.add(1, 9) arr.add_first(100) val = arr.remove_last() # 100 1 9 2 3 for i in range(arr.get_size()): print(arr.get(i))

数组的优点和局限性

优点

• 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
• 支持随机访问：数组允许在 O(1) 时间内访问任何元素。
• 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

局限性

• 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
• 长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
• 空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

数组的应用 

• 随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。
• 排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
• 查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。
• 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。
• 数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。