1、动态数组(array)

1、数组(array vs list)

array: 定长，操作有限，但是节省内存，可以用import array直接导入

list: 会预先分配内存，操作丰富，但是耗费内存。

• list.append: 如果之前没有分配够内存，会重新开辟新区域，然后复制之前的数据，复杂度退化
• list.insert: 会移动被插入区域后所有元素，O(n)
• list.pop: pop不同位置需要的复杂度不同pop(0)是O(1)复杂度，pop()是O(n)复杂度
• list[]: slice操作copy数据（预留空间）到另一个list

数组的特点：

• 占用一段连续内存空间，支持随机(索引)访问，且时间复杂度为: O(1)
• 添加、删除元素的时间复杂度为：O(n)

基于 Python list自己实现一个动态数组类 Array：

# -*- coding: utf-8 -*-
"""
Description： 数组
"""
class Array(object):
"""数组类定义"""
def __init__(self, capacity=10):
"""初始化一个固定大小的空数组，默认数组大小为 10"""
self._size = 0
# 数组有效元素的个数，初始化为0
self._capacity = capacity
# 由于 Python 的 list 是动态扩展的，而我们要实现的层具有固定容量，
# 占用一段连续的内存空间的数组，所以用 None 来作为无效元素的标识
self._data = [None] * self._capacity
def __getitem__(self, index: int):
"""让 Array 支持索引"""
assert 0 <= index < len(self._data), 'out of range'
return self._data[index]
def __setitem__(self, index: int, value):
"""修改数组指定位置的值"""
assert 0 <= index < len(self._data), 'out of range'
self._data[index] = value
def __iter__(self):
for item in self._data:
yield item
def __len__(self):
return self._size
def _resize(self, new_capacity):
"""数组容量缩放至 new_capacity，私有成员函数"""
new_arr = Array(new_capacity)
for i in range(self._size):
new_arr.insert_last(self._data[i])
self._capacity = new_capacity
self._data = new_arr._data
def get_size(self):
"""获取有效元素的个数"""
return self._size
def get_capacity(self):
return self._capacity
def is_empty(self):
return self._size == 0
def find(self, elem):
"""在数组中查找元素，并返回元素所在的索引；
如果数组中存在多个 elem，则只返回最左边的 elem 的索引;
如果数组中不存在元素 elem，则返回-1
时间复杂度：O(n)
"""
for i in range(self._size):
if self._data[i] == elem:
return i
return -1
def find_all(self, elem):
"""找到数组中值为 elem 的全部元素的索引，以列表的形式返回"""
ret_list = Array()
for i in range(self._size):
if self._data[i] == elem:
ret_list.insert_last(i)
return ret_list
def remove(self, index: int):
"""删除索引为 index 的元素，并返回删除元素的值
index 后面的元素都要向前移动一个位置
时间复杂度：O(n)
"""
if index < 0 or index >= self._size:
raise Exception("remove failed. require 0 < index < self._size")
ret = self._data[index]
for i in range(index + 1, self._size):
self._data[i - 1] = self._data[i]
self._size -= 1
self._data[self._size] = None
# 如果当前有效元素个数为总容量的四分之一，且还存在有效元素
if self._size and self._capacity // self._size == 4:
self._resize(self._capacity // 2)
return ret
def remove_firt(self):
"""删除数组的首位元素"""
self.remove(0)
def remove_last(self):
"""删除数组的末尾元素"""
self.remove(self._size -1)
def remove_element(self, elem):
"""删除数组中值为 elem 的元素，如果数组中不存在元素 elem 则什么都不做，
如果存在多个相同的 elem，则只删除最左边的那个。
时间复杂度： O(n)
"""
index = self.find(elem)
if index != -1:
self.remove(index)
def remove_all(self, elem):
"""删除数组内所有值为 elem 的元素，可以用递归来写
这里使用迭代的方式实现，elem 不存在，则什么都不做
"""
while True:
index = self.find(elem)
if index != -1:
self.remove(index)
else:
break
def insert(self, index: int, elem):
"""
向数组中添加一个元素，注意数组占用的是一段连续的内存空间，所以在添加元素后，
数组还是要保证这个特点的，因此需要将后面的元素都向后挪一个位置，而且要注意要先从
尾部开始挪，防止元素之间的覆盖
时间复杂度：O(n)
:param index:
添加的元素所在的索引
:param elem:
所要添加的元素
"""
if index < 0 or index > self._size:
# 插入的位置无效
raise Exception('Add Filed. Require 0 <= index <= self._size')
if self._size == self._capacity:
# 满了
# 默认扩容当前容量的二倍。容量翻倍要比容量加上一个固定值要好，这样做均摊复杂度为O(1)。
self._resize(self._capacity * 2)
for i in range(self._size - 1, index - 1, -1):
# 从尾部开始挪动元素，在index处腾出一个空间
# 一定要注意在步长为负数的情况下，区间是左开右闭区间，即(index, self._size - 1]，所以是index-1，与正常的左闭右开区间是相反的！
self._data[i + 1] = self._data[i]
self._data[index] = elem
# 将该位置赋值为elem
self._size += 1
# 数组有效元素数加1
def insert_last(self, elem):
"""尾部插入，时间复杂度 O(1)"""
self.insert(self._size, elem)
def insert_first(self, elem):
"""头部插入，时间复杂度 O(1)"""
self.insert(0, elem)
def get(self, index):
"""获取索引 index 处的元素
时间复杂度 O(1)
"""
if index < 0 or index >= self._size:
raise Exception("get fail. index is illegal")
return self._data[index]
def get_first(self):
"""获取数组首位元素"""
return self.get(0)
def get_last(self):
"""获取数组末尾元素"""
return self.get(self._size - 1)
def set(self, index, elem):
"""将索引 index 位置的元素值修改为 elem"""
if index < 0 or index >= self._size:
raise Exception('set fail. index is illegal')
self._data[index] = elem
def contains(self, elem):
"""查看数组中是否存在元素 elem，最好不要传入一个浮点数
时间复杂度：O(n)
"""
for i in range(self._size):
if self._data[i] == elem:
return True
return False
def print_all(self):
print("[", end=" ")
for item in self._data:
print(item, end=" ")
print("]")
def test():
arr = Array(5)
arr.insert(0, 3)
arr.insert(0, 4)
arr.insert(1, 5)
arr.insert(3, 9)
arr.insert(3, 10)
# assert arr.insert(0, 100) is False
# 超过数组的大小
assert len(arr) == 5
# assert arr.find(1) == 5
# assert arr.remove(4) is True
arr.print_all()
if __name__ == '__main__':
test()

最后

以上就是幸福路人最近收集整理的关于1、动态数组(array)的全部内容，更多相关1、动态数组(array)内容请搜索靠谱客的其他文章。