第一章——数组基础（概念篇python版）

见贤思齐

目录一、数组基础二、数组基本操作的具体实现2.1向数组中添加元素（增）2.2根据索引获取元素值（查）2.3根据元素值去查数组（查）2.3.1根据值查看数组中是否存在该元素2.3.2根据值返回元素的索引2.4获取数组中最大值（最小值）的索引（查）2.5根据索引修改元素值（改）2.6交换两个元素（改）2.7从数组中删除元素（删）2.8根据元素值删除该元素（查+删）2.9删除数组中值最大（最小）的元素（查+删）三、动态数组3.1基本概念3.2动态数组时间复杂度分析3.2.1添加操作O(n)3.2.2删除操作O(n)3.2.3修改操作O(1)3.2.4查询操作3.2.5总结3.3动态数组均摊复杂度3.4Python列表与字典操作时间复杂度3.4.1列表操作时间复杂度3.4.2字典操作时间复杂度一、数组基础官方定义：将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。翻译：将数据码成一排进行存放索引可以有语义，索引也可以没有语义数组最大的优点：快速查询，时间复杂度O(1)数组最好应用于“索引有语义”的情况但是并不是所有有语义的索引都适用比如身份证号：13131413415153数组也可以处理没有语义的情况我们在这一章，主要处理索引没有语义的情况数组的使用索引没有语义，如何表示没有元素？如何添加元素？如何删除元素？我们可以自己定义一个Array类，来实现一些简单的功能定义自己的数组类："""数组特点：占用一段连续的内存空间，支持随机(索引)访问，且时间复杂度为O(1)添加元素时间复杂度：O(n)删除元素时间复杂度：O(n)"""classArr:def__init__(self,capacity=10):"""构造函数:paramcapacity:数组最大容量，不指定的话默认为10"""self._capacity=capacity#数组的有效元素数目，初始化为0self._size=0#由于python的list是动态扩展的，而我们要实现底层具有固定容量，#占用一段连续内存空间的数组，所以用None来作为无效元素的标识self._data=[None]*self._capacitydef__getitem__(self,item):"""让Arr类支持索引操作:paramitem:索引:return:该索引对应位置上的元素值"""returnself._data[item]defgetSize(self):"""返回数组有效元素的个数:return:数组有效元素的个数"""returnself._sizedefgetCapacity(self):"""返回数组的容量:return:数组的容量"""returnself._capacitydefisEmpty(self):"""判断数组是否为空:return:True为空，False为非空"""returnself._size==0defprintArr(self):"""对数组元素进行打印"""foriinrange(self._size):print(self._data[i],end='')print('\nSize:%d------Capacity:%d'%(self.getSize(),self.getCapacity()))1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556二、数组基本操作的具体实现2.1向数组中添加元素（增）defadd(self,index,elem):"""向数组中添加一个元素，注意数组占用的是一段连续的内存空间，所以在添加元素后，数组还是要保证这个特点，因此需要将后面的元素都向后挪一个位置而且注意需要从尾部开始挪，防止元素之间的覆盖时间复杂度：O(n):paramindex:添加元素所在的索引位置:paramelem:所要添加的元素值"""#判断插入的位置是否无效ifindexself._size:raiseException('AddFailed.Require0=self._size:raiseException('GetFailed.Indexisillegal.')returnself._data[index]1234567891011由此可写出两个特殊函数，为获取头部和尾部元素的函数，直接调用get函数即可：defgetFirst(self):"""获得数组首位元素的值:return:首位元素的值"""#直接调用get函数，安全可靠returnself.get(0)defgetLast(self):"""获得数组末尾元素的值:return:末尾元素的值"""#直接调用get函数，安全可靠returnself.get(self._size-1)1234567891011121314152.3根据元素值去查数组（查）2.3.1根据值查看数组中是否存在该元素defcontains(self,elem):"""查看数组中是否存在元素elem，最好不要传入一个浮点数时间复杂度：O(n):paramelem:目标元素:return:bool值，存在为真"""#遍历数组foriinrange(self._size):ifself._data[i]==elem:#找到了就返回TruereturnTrue#遍历完了还没找到，返回FalsereturnFalse12345678910111213142.3.2根据值返回元素的索引deffind(self,elem):"""在数组中查找元素，并返回元素所在的索引。如果数组中存在多个elem，只返回最左边elem的索引时间复杂度：O(n):paramelem:目标元素:return:元素所在的索引，没找到则返回-1（无效值）"""#遍历数组foriinrange(self._size):ifself._data[i]==elem:#找到就返回索引returni#没找到就返回-1return-1deffindAll(self,elem):"""找到值为elem全部元素的索引时间复杂度：O(n):paramelem:目标元素:return:一个列表，值为全部elem的索引"""#建立一个新的数组用于存储索引值ret_list=Arr()#遍历数组foriinrange(self._size):ifself._data[i]==elem:#找到就将索引添加进ret_listret_list.addLast(i)returnret_list123456789101112131415161718192021222324252627282930312.4获取数组中最大值（最小值）的索引（查）defget_Max_index(self):"""获取数组中的最大元素的索引，返回最大元素的索引值如果有多个最大值，默认返回最左边的那个索引时间复杂度：O(n):return:最大元素的索引"""ifself.isEmpty():raiseException('Error,arrayisEmpty!')#记录最大值的索引，初始化为0max_elem_index=0#从索引1开始遍历，一直到数组尾部foriinrange(1,self._size):#如果当前索引的值大于最大值索引处元素的值ifself._data[i]>self._data[max_elem_index]:#更新max_elem_index，这样它还是当前最大值的索引max_elem_index=i#遍历完后，将数组的最大值索引返回returnmax_elem_indexdefget_Min_index(self):"""获取数组中的最小元素的索引，返回最小元素的索引值如果有多个最小值，默认返回最左边的那个索引时间复杂度：O(n):return:最小元素的索引"""ifself.isEmpty():raiseException('Error,arrayisEmpty!')#记录最小值的索引，初始化为0min_elem_index=0#从索引1开始遍历，一直到数组尾部foriinrange(1,self._size):#如果当前索引的值小于最小值索引处元素的值ifself._data[i]=self._size:raiseException('SetFailed.Indexisillegal.')self._data[index]=elem12345678910112.6交换两个元素（改）defswap(self,index1,index2):"""交换分别位于索引index1和索引index2处的元素时间复杂度：O(1):paramindex1:索引1:paramindex2:索引2"""#合法性检查ifindex1=self._sizeorindex2>=self._size:raiseException('Indexisillegal')#交换元素self._data[index1],self._data[index2]=self._data[index2],self._data[index1]1234567891011122.7从数组中删除元素（删）删除指定位置的元素，删除索引为1的元素：defremove(self,index):"""删除索引为index的元素。index后面的元素都要向前移动一个位置时间复杂度：O(n):paramindex:目标索引:return:位于该索引的元素的值"""#index合法性检查ifindex=self._size:raiseException('RemoveFailed.Require0