数组：将数据元素顺序的存储在一片连续的存储区里，元素之间的顺序关系由它们的存储顺序决定
数组最大的优点：可以快速查询
自定义一个数组
静态数组的实现
静态数组是指数组的容量是固定的，
class Array:
def __init__(self, capacity=10):
self._capacity = capacity
self._size = 0
self._data = [None] * self._capacity # 构造一段连续的固定空间
def __getitem__(self, item):
# 使数组支持索引操作
return self._data[item]
def getSize(self):
return self._size
def getCapacity(self):
return self._capacity
def isEmpty(self):
return self._size == 0
def addLast(self, elem):
if self._size == self._capacity:
raise Exception("array已经满了，不能再往里添加元素！")
self._data[self._size] = elem
self._size += 1
# 可以直接调用add函数
# self.add(self._size,elem)
def add(self, index, elem):
if index < 0 or index > self._size:
raise Exception("索引值错误！")
if self._size == self._capacity:
raise Exception("array已经满了，不能再往里添加元素！")
for i in range(self._size, index, -1): # 这里i不能到index，只能到inde+1
self._data[i] = self._data[i - 1]
# 注意这里就算是插入的位置为0，不能哪种方法实现，都可以，因为range不包含最后一个数
# for i in range(self._size-1,index-1,-1):
# self._data[i+1] = self._data[i]
self._data[index] = elem
self._size += 1
def addFirst(self, elem):
self.add(0, elem)
def get(self, index):
if index < 0 or index >= self._size:
# 判断索引的时候要列表大小，因为索引值最大为元素长度-1
raise Exception("索引值错误！")
return self._data[index]
def getFirst(self):
return self.get(0)
def getLast(self):
return self.get(self._size - 1)
def set(self, index, elem):
if index < 0 or index >= self._size:
raise Exception("索引错误！")
self._data[index] = elem
def contains(self, ele):
for i in range(self._size):
if self._data[i] == ele:
return True
return False
def find(self, ele):
for i in range(self._size):
if self._data[i] == ele:
return i
return -1
def findAll(self, ele):
res = Array()
for i in range(self._size):
if self._data[i] == ele:
res.addLast(i)
return res
def remove(self, index):
if index < 0 or index >= self._size:
# 对于空列表，移除0位置，则index>=self._size成立
raise Exception("索引错误！")
ret = self._data[index]
for i in range(index, self._size + 1):
self._data[i] = self._data[i + 1]
self._size -= 1
return ret
def removeFirst(self):
return self.remove(0)
def removeLast(self):
return self.remove(self._size - 1)
def removeElement(self, elem):
index = self.find(elem)
if index != -1:
self.remove(index)
else:
print("该元素在列表中不存在！")
def removeAllElement(self, elem):
while True:
index = self.find(elem)
if index != -1:
self.remove(index)
else:
break
def get_Max_index(self):
if self.isEmpty():
raise Exception("这是一个空列表，没有最大值！")
max_elem_index = 0
for i in range(1, self._size):
if self._data[i] > self._data[max_elem_index]:
max_elem_index = i
return max_elem_index
def removeMax(self):
index = self.get_Max_index()
return self.remove(index)
def get_Min_index(self):
if self.isEmpty():
raise Exception("这是一个空列表，没有最大值！")
min_elem_index = 0
for i in range(1, self._size):
if self._data[i] < self._data[min_elem_index]:
min_elem_index = i
return min_elem_index
def removeMin(self):
return self.remove(self.get_Min_index())
def swap(self, index1, index2):
if index1 < 0 or index1 >= self._size or index2 < 0 or index2 >= self._size:
raise Exception("索引错误！")
self._data[index1], self._data[index2] = self._data[index2], self._data[index1]
def printArr(self):
for i in range(self._size):
print(self._data[i], end=' ')
print('nSize:%d-----------Capacity:%d' % (self.getSize(), self.getCapacity()))
动态数组
class Array:
def __init__(self, capacity=10):
self._capacity = capacity
self._size = 0
self._data = [None] * self._capacity # 构造一段连续的固定空间
def __getitem__(self, item):
# 使数组支持索引操作
return self._data[item]
def getSize(self):
return self._size
def getCapacity(self):
return self._capacity
def isEmpty(self):
return self._size == 0
def addLast(self, elem):
self.add(self._size, elem)
# 和静态数组的最大区别就是添加了一个resize操作
def _resize(self, new_capacity):
new_arr = Array(new_capacity)
for i in range(self._size):
new_arr.addLast(self._data[i])
self._capacity = new_capacity
self._data = new_arr._data
def add(self, index, elem):
if index < 0 or index > self._size:
raise Exception("索引值错误！")
if self._size == self._capacity:
self._resize(self._capacity * 2)
# raise Exception("array已经满了，不能再往里添加元素！")
for i in range(self._size, index, -1): # 这里i不能到index，只能到inde+1
self._data[i] = self._data[i - 1]
# 注意这里就算是插入的位置为0，不能哪种方法实现，都可以，因为range不包含最后一个数
# for i in range(self._size-1,index-1,-1):
# self._data[i+1] = self._data[i]
self._data[index] = elem
self._size += 1
def addFirst(self, elem):
self.add(0, elem)
def get(self, index):
if index < 0 or index >= self._size:
# 判断索引的时候要列表大小，因为索引值最大为元素长度-1
raise Exception("索引值错误！")
return self._data[index]
def getFirst(self):
return self.get(0)
def getLast(self):
return self.get(self._size - 1)
def set(self, index, elem):
if index < 0 or index >= self._size:
raise Exception("索引错误！")
self._data[index] = elem
def contains(self, ele):
for i in range(self._size):
if self._data[i] == ele:
return True
return False
def find(self, ele):
for i in range(self._size):
if self._data[i] == ele:
return i
return -1
def findAll(self, ele):
res = Array()
for i in range(self._size):
if self._data[i] == ele:
res.addLast(i)
return res
def remove(self, index):
if index < 0 or index >= self._size:
# 对于空列表，移除0位置，则index>=self._size成立
raise Exception("索引错误！")
ret = self._data[index]
for i in range(index, self._size + 1):
self._data[i] = self._data[i + 1]
self._size -= 1
#可能会引起后文提到的复杂度震荡，因此将缩容时候更改为1/4时再缩容
#if self._size and self._capacity // self._size == 2:
if self._size and self._capacity // self._size == 4:
self._resize(self._capacity // 2)
return ret
def removeFirst(self):
return self.remove(0)
def removeLast(self):
return self.remove(self._size - 1)
def removeElement(self, elem):
index = self.find(elem)
if index != -1:
self.remove(index)
else:
print("该元素在列表中不存在！")
def removeAllElement(self, elem):
while True:
index = self.find(elem)
if index != -1:
self.remove(index)
else:
break
def get_Max_index(self):
if self.isEmpty():
raise Exception("这是一个空列表，没有最大值！")
max_elem_index = 0
for i in range(1, self._size):
if self._data[i] > self._data[max_elem_index]:
max_elem_index = i
return max_elem_index
def removeMax(self):
index = self.get_Max_index()
return self.remove(index)
def get_Min_index(self):
if self.isEmpty():
raise Exception("这是一个空列表，没有最大值！")
min_elem_index = 0
for i in range(1, self._size):
if self._data[i] < self._data[min_elem_index]:
min_elem_index = i
return min_elem_index
def removeMin(self):
return self.remove(self.get_Min_index())
def swap(self, index1, index2):
if index1 < 0 or index1 >= self._size or index2 < 0 or index2 >= self._size:
raise Exception("索引错误！")
self._data[index1], self._data[index2] = self._data[index2], self._data[index1]
def printArr(self):
for i in range(self._size):
print(self._data[i], end=' ')
print('nSize:%d-----------Capacity:%d' % (self.getSize(), self.getCapacity()))
时间复杂度：
对于数组而言，时间复杂度中所指的n是该数组中元素的个数
增、删：O(n)
对于增删，如果在最后一个位置增删的话，时间复杂度为O(1)，但是如果调用了resize操作，那么时间复杂度就是O(n)，因此最坏时间复杂度就是O(n)
改：已知索引O(1)、未知索引O(n)
查：已知索引O(1)、未知索引O(n)
一般说的时间复杂度都是指最坏时间复杂度
动态数组均摊复杂度
如果每次只是在数组的最后一个位置添加
例如，capacity=8，添加8次该数组满了，添加第九次的时候，触发了resize，那么进行了8次的元素转移，总共9次添加+8次数据转移
capacity=m，m+1次添加，m次转移，总共进行了2m+1次基本操作，平均每次添加操作进行2次基本操作，即均摊复杂度为O(1)
总之，多少次触发一次O(n) ，那么这几次操作均摊这O(n)
对于动态数组，如果数组满了，那么就会触发resize操作进行扩容，容量变成原来的2倍，刚刚扩容后紧接着进行删除一个元素，那么，这是元素的个数<=容量的1/2，又将会进行缩容，这样每次都将进行时间复杂度为O(n) 的操作
Python列表与字典操作的时间复杂度
注意，contains的时间复杂度为O(1)
