【算法】看完两道大厂面试题，泪流满面“重新学习数组”

今日目录：1：能说出线性表的概念2：能说出数组的存储结构3：能说出数组的特性查询、插入、删除操作及相应的时间复杂度4：可以完成动态数组ArrayList的代码编写1.线性表在数据结构中，数据的逻辑结构分为线性结构和非线性结构。线性结构：n个数据元素的有序（ordered）集合。其特点如下：1、集合中必须只有一个“第一元素”；2.集合中必须只有一个“最后一个元素”；3、除最后一个元素外，其他数据元素都有唯一的“后继者”；4.除第一个元素外，其他数据元素都有唯一的“前身”。数据结构中的线性结构是指数据元素之间存在“一对一”线性关系的数据结构。当然，这种线性并不是说一定是直线。常见的线性数据结构包括：数组（一维）、链表、栈、队列；它们也是我们后续学习其他数据结构的基础。表达式如下：对应线性结构，非线性结构的逻辑特点是一个节点元素可能对应多个直接前驱和多个后继，比如后续要学习的：树，图，堆等，如图2，数组基础2.1，概念与结构数组（Array）是一种线性数据结构，它使用连续的内存空间来存储相同数据类型的数据。int[]array=newint[]{10,20,30}int[]array=newint[6];数组的表示：使用下标获取数组元素数据找到对应元素的内存地址呢？我们以一个长度为10的数组为例，int[]a=newint[10]，下图中，计算机为数组分配了一个连续的空间，100-139，这里是内存的起始地址就是baseAddress=100我们知道计算机给每一个内存单元都分配了一个地址，它的数据是通过地址来访问的，所以在访问数组中的元素时，首先要计算出内存中要访问的元素是通过寻址公式Address：a[i]=baseAddress+i*dataTypeSize其中dataTypeSize表示数组中元素类型的大小。本例中存储的是int类型的数据，所以dataTypeSize=4bytes为什么下标从0开始而不是Not1呢？从数组存储的内存模型来看，“下标”最准确的定义应该是“偏移量”。前面说过，如果用array表示数组首地址，array[0]就是偏移量为0的位置，即首地址，array[k]表示偏移量为k的位置type_size，所以计算array[k]的内存地址只需要用到这个公式：array[k]_address=base_address+k*type_size但是如果下标从1开始，那么计算array[k]的内存地址就变成了:array[k]_address=base_address+(k-1)*type_size对比两个公式不难发现，如果数组下标从1开始按照下标访问数组元素，对于CPU来说，有又是一条减法指令。当然，另一方面，由于历史的原因，C语言的设计者将0作为数组的下标，后来的高级语言也沿用了这种设计。2.2.数组的特点2.2.1。查询O(1)数组元素通过下标访问。计算机可以通过数组首地址和寻址公式快速找到你要访问的元素publicinttest01(int[]a,inti){returna[i];//a[i]=baseAddress+i*dataSize}代码的执行次数不会随着数组的数据大小而变化，是一个常量级别，所以查询数据操作的时间复杂度为O(1)2.2.2、插入和删除O(n)数组是一个连续的内存空间，所以为了保证数组的连续性，数组的插入和删除的效率会变的很低。数据插入：假设数组的长度为n，现在如果我们需要向数组的第k个位置插入一条数据。为了腾出第k个位置给新数据，我们需要将第k到第n部分的元素依次向后移动一位。如下图所示：插入操作的时间复杂度是多少？最好的情况是O(1)，最坏的情况是O(n)，平均情况下的时间复杂度是O(n)。数据删除：同理可得：如果我们要删除第k个位置的数据，为了内存的连续性，也需要移动数据，否则中间会出现空洞，内存不连续的，时间复杂度还是O(n)。想想用什么场景来提高数据删除的效率？其实在一些特殊的场景下，我们不一定要追求数组中数据的连续性。如果我们一起进行多次删除操作，删除的效率是不是会提高很多呢？例如，数组a[6]中存储了6个元素：a1、a2、a3、a4、a5、a6。现在，我们要依次删除a1、a2这两个元素。为了避免a3、a4、a5、a6的数据被移动两次，我们可以先记录删除的数据。每次删除操作实际上并不移动数据，而只是记录数据已被删除。当数组没有更多空间存储数据时，我们触发真正的删除操作，大大减少了删除操作带来的数据移动。对于这个思路，不就是JVMmarkcleargarbagecollection算法的核心思想吗？这其实告诉我们，我们不需要死记硬背一个数据结构或者算法，而是去理解和学习它背后的思维和处理技巧。3、面试实战3.1、11：最装水的容器华为、腾讯近期面试题：11：最装水的容器1：暴力破解，简单解法classSolution{//暴力破解方法列举所有坐标组合，找到每个组合publicintmaxArea(int[]height){//定义水的最大值intmax=0;for(inti=0;i休息？资源：休息；}返回资源；移零1：双指针（快慢指针），一维数组类的下标变换操作思路解{//双指针移动时间复杂度O(n)空间复杂度O(1)publicvoidmoveZeroes(int[]nums){if(nums==null||nums.length<2){return;}//从前到后指向非零元素的指针intp1=0;对于(inti=0;i0){this.elementData=新的int[initCapaticy];}else{thrownewIllegalArgumentException("initCapaticyerror"+initCapaticy);}}(5)完成大小、isEmpty、indexOf、contains等方法@Overridepublicintsize(){returnsize;}@OverridepublicbooleanisEmpty(){returnsize==0;}@OverridepublicintindexOf(into){for(inti=0;i=0;}(6)完成向容器尾部添加元素的方法add，涉及容器的动态扩展@Overridepublic布尔添加（inte）{//在添加ensureCapacity(size+1)之前确保容量是否足够；this.elementData[size++]=e;返回true；}privatevoidensureCapacity（intminCapacity）{如果（minCapacity>this.elementData.length）{grow（minCapacity）；}}privatevoidgrow(intminCapacity){intoldCapacity=this.elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);如果（新容量<最小容量）{新容量=最小容量；}//使用new创建一个容量大小的新数组，将原数组中的数据复制到新数组中，并使this.elementData指向新数组copyOf(newCapacity);}privatevoidcopyOf(intnewCapacity){int[]newarray=newint[newCapacity];System.arraycopy(this.elementData,0,newarray,0,size);this.elementData=newarray;}(7)完成add(intindex,intelement),set(intindex,intelement),get(intindex)方法，在方法中，先检查索引位置是否合理，然后检查是否需要扩展，最后在指定索引位置插入一个元素@Overridepublicvoidadd(intindex,intelement){rangeCheck(index);//因为要添加一个元素，之前的元素不会被覆盖，只会向后移动，所以可以扩大ensureCapacity(size+1);//展开完成后，index处的元素将依次向后移动System.arraycopy(this.elementData,index,this.elementData,index+1,size-index);//将数据存储在索引处this.elementData[index]=element;大小++；}@Overridepublicintset(intindex,intelement){rangeCheck(index);intoldElement=this.elementData[index];this.elementData[index]=元素；返回旧元素；}privatevoidrangeCheck(intindex){if(index<0||index>size){thrownewIndexOutOfBoundsException("index:"+index+",size="+this.size);}}@Overridepublicintget(intindex){rangeCheck(index);returnthis.elementData[index];}(8)completeremove(intindex),clear@Overridepublicintremove(intindex){rangeCheck(index);intoldValue=this.elementData[索引];//移动的元素个数intmoveCount=size-index-1;System.arraycopy(this.elementData,index+1,this.elementData,index,moveCount);//清除最后一个位置的元素this.元素数据[大小-1]=0;//容器中元素个数-1尺寸-;返回旧值；}@Overridepublicvoidclear(){for(inti=0;i