咱也不知道咋想的，周末的的时候闲来没事，因为看到一道数组的面试题，我就跟数组杠上了，问题也不大，就是一个数组重写的问题，我不知道大家有没有遇到过类似的问题，在日常的开发环境中，反正我是没遇到过，正常的开发就行，可能是因为我公司业务的原因吧，哈哈哈哈

但是，我个人的爱好就是会看一些面试题，去考察自己的知识点掌握情况，以及和市场的动态，建议大家也可以这样试一下，保持自己的竞争力，所以，在看到这道面试题之后，我就想去试一下，然后就有了下面的代码详解

看正式代码之前，关注我给我点动力吧，让我能更好的往下创作，

个人公众号：Java架构师联盟，每日更新技术好文

嘿嘿嘿，好了，说正事

int类型数组

publicclassMain{

​

publicstaticvoidmain(String[]args) {

Arrayscore=newArray(10);

for(inti=0;i<8;i++){

score.addLast(i);

       }

​

score.add(1,100);

score.addLast(99);

System.out.println(score.toString());

​

System.out.println(score.find(1));

System.out.println(score.contains(1));

System.out.println(score.remove(1));

System.out.println(score.toString());

System.out.println(score.removeElement(2));

System.out.println(score.toString());

   }

}

​

修改为泛型

publicclassArray<T>{

privateT[]data;

privateintsize;

​

publicArray() {

this(10);

   }

​

publicArray(intcapacity) {

//java本身不支持直接new 一个泛型数组，所以用以下方法实现

data=(T[])newObject[capacity];

size=0;

   }

​

publicintgetSize() {

returnsize;

   }

​

publicintgetCapacity() {

returndata.length;

   }

​

publicbooleanisEmpty() {

returnsize==0;

   }

​

/**

* 向数组末尾添加元素

*

* @param e

*/

publicvoidaddLast(Te) {

add(size,e);

   }

​

/**

* 向数组开头添加元素

*

* @param e

*/

publicvoidaddFirst(Te) {

add(0,e);

   }

​

/**

* 向任意合法位置添加元素

*

* @param index

* @param e

*/

publicvoidadd(intindex,Te) {

if(size==data.length) {

thrownewIllegalArgumentException("Add is fail.Array is full");

       }

​

if(index<0||index>size) {

thrownewIllegalArgumentException("Add is fail.Require index >= 0 and index < size");

       }

​

for(inti=size;i>index;i--) {

data[i]=data[i-1];

       }

data[index]=e;

size++;

   }

​

/**

* 获取索引位置的元素

* 通过这种封装，用户无法查询未使用的空间，保证了数据的安全性。

*

* @param index

* @return

*/

publicTget(intindex) {

if(index<0||index>=size) {

thrownewIllegalArgumentException("Get is failed.Index is illegal");

       }

returndata[index];

   }

​

/**

* 修改索引位置的元素

*

* @param index

* @param e

*/

publicvoidset(intindex,Te) {

if(index<0||index>=size) {

thrownewIllegalArgumentException("Set is failed.Index is illegal");

       }

data[index]=e;

   }

​

/**

* 数组中是否包含某个元素

*

* @param e

* @return

*/

publicbooleancontains(Te) {

for(inti=0;i<size;i++) {

//注意值的比较应修改为equals方法

if(data[i].equals(e)) {

returntrue;

           }

       }

returnfalse;

   }

​

/**

* 查询数组中某个元素的索引

*

* @param e

* @return 没有该元素则返回-1

*/

publicintfind(Te) {

for(inti=0;i<size;i++) {

if(data[i].equals(e)) {

returni;

           }

       }

return-1;

   }

​

/**

* 删除index位置的元素，并且返回该元素

* 不用担心删除后原来size位置的元素，因为用无法访问到它。

* 但是最好再写一句data[size]=null 具体原因需要了解java的垃圾回收机制

*

* @param index

* @return

*/

publicTremove(intindex) {

if(index<0||index>=size) {

thrownewIllegalArgumentException("Remove failed.Require index >=0 and index < size");

       }

​

Tret=data[index];

for(inti=index;i<size-1;i++) {

data[i]=data[i+1];

       }

//注意维护size

size--;

data[size]=null;

returnret;

   }

​

/**

* 不用担心数组为空的情况，因为数组如果为空,remove方法就会抛出异常

* @return

*/

publicTremoveFirst(){

returnremove(0);

   }

​

publicTremoveLast(){

returnremove(size-1);

   }

​

/**

* 从数组中删除元素e

* @param e

*/

publicbooleanremoveElement(Te){

intindex=find(e);

if(index!=-1){

remove(index);

returntrue;

}else{

returnfalse;

       }

   }

​

/**

* 重写toString()方法

*

* @return

*/

@Override

publicStringtoString() {

StringBuilderres=newStringBuilder();

res.append(String.format("size= %d,capacity= %d\n",size,data.length));

res.append("[");

for(inti=0;i<size;i++) {

res.append(data[i]);

if(i!=size-1) {

res.append(",");

           }

       }

res.append("]");

returnres.toString();

   }

}

增加数组大小

前面当我们向数组中添加元素时，如果index==size，表示数组已满。

if(size==data.length) {

thrownewIllegalArgumentException("Add is fail.Array is full");

}

现在可以考虑这样做，依然判断插入位置是否合法，但是当size等于数组长度时，自动为数组扩容——resize(2*data.length);之所以是扩为原来的2倍，是因为这样扩容量的大小和原来容量大小有关，既不会过小也不会过大。

privatevoidresize(intnewCapacity){

T[]newData=(T[])newObject[newCapacity];

for(inti=0;i<size;i++){

newData[i]=data[i];

   }

data=newData;

}

减小数组大小

因为有了resize方法，实现起来就很简单了。在remove(int index)方法中，移除一个元素且维护size后，再加上对维护后的size的判断，如下。如果size已经变为capacity的一半，则将数组容量减半。

if(size==data.length/2){

resize(data.length/2);

}

注意resize()方法设为私有，是为了用户只需使用这个数组类，不必去顾虑数组的大小。

时间复杂度的分析

通过对addLast(T[] e)和removeLast(T[] e)时间复杂度的分析，我们发现都是O(n)级别的。但是，这样一般性的考虑最坏的情况在这种情景下是没有太大意义的。因为addLast(T[] e)和removeLast(T[] e)操作并不会经常触发resize(int newCapcity)操作。所以用均摊复杂度分析的话，你会发现这两个操作的均摊复杂度都是O(1)。因此resize(int newCapcity)这样一个比较耗时的操作，如果保证不会每次都会触发，就可以将它的操作耗时分摊到其他操作上。

现在再考虑另外一个场景，就是在addLast(T[] e)操作后，触发了resize(int newCapcity)，然后再removeLast(T[] e)，又触发了resize(int newCapcity)；如此循环。像这样addLast(T[] e)和removeLast(T[] e)的时间复杂度都是O(n)级别的，这就是所谓的复杂度的震荡。以数组这个例子，之所以发生这种情况是因为我们在removeLast操作后，就接着进行了resize操作这样太着急了。那么该如何防止复杂度的震荡呢？可以这样修改removeLast方法的代码。

if(size==data.length/4&&data.length/4!=0){

    resize(data.length/2);

}

加上data.length/4!=0的判断是因为当data.length/4==0的时候，数组长度变为0，这是不合法的。

修改后的完整代码

publicclassArray<T>{

privateT[]data;

privateintsize;

​

publicArray() {

this(10);

   }

​

publicArray(intcapacity) {

//java本身不支持直接new 一个泛型数组，所以用以下方法实现

data=(T[])newObject[capacity];

size=0;

   }

​

publicintgetSize() {

returnsize;

   }

​

publicintgetCapacity() {

returndata.length;

   }

​

publicbooleanisEmpty() {

returnsize==0;

   }

​

/**

* 向数组末尾添加元素

*

* @param e

*/

publicvoidaddLast(Te) {

add(size,e);

   }

​

/**

* 向数组开头添加元素

*

* @param e

*/

publicvoidaddFirst(Te) {

add(0,e);

   }

​

/**

* 向任意合法位置添加元素

*

* @param index

* @param e

*/

publicvoidadd(intindex,Te) {

/*if (size == data.length) {

throw new IllegalArgumentException("Add is fail.Array is full");

}*/

​

if(index<0||index>size) {

thrownewIllegalArgumentException("Add is fail.Require index >= 0 and index < size");

       }

​

if(size==data.length){

resize(2*data.length);

       }

​

for(inti=size;i>index;i--) {

data[i]=data[i-1];

       }

data[index]=e;

size++;

   }

​

/**

* 获取索引位置的元素

* 通过这种封装，用户无法查询未使用的空间，保证了数据的安全性。

*

* @param index

* @return

*/

publicTget(intindex) {

if(index<0||index>=size) {

thrownewIllegalArgumentException("Get is failed.Index is illegal");

       }

returndata[index];

   }

​

/**

* 修改索引位置的元素

*

* @param index

* @param e

*/

publicvoidset(intindex,Te) {

if(index<0||index>=size) {

thrownewIllegalArgumentException("Set is failed.Index is illegal");

       }

data[index]=e;

   }

​

/**

* 数组中是否包含某个元素

*

* @param e

* @return

*/

publicbooleancontains(Te) {

for(inti=0;i<size;i++) {

//注意值的比较应修改为equals方法

if(data[i].equals(e)) {

returntrue;

           }

       }

returnfalse;

   }

​

/**

* 查询数组中某个元素的索引

*

* @param e

* @return 没有该元素则返回-1

*/

publicintfind(Te) {

for(inti=0;i<size;i++) {

if(data[i].equals(e)) {

returni;

           }

       }

return-1;

   }

​

/**

* 删除index位置的元素，并且返回该元素

* 不用担心删除后原来size位置的元素，因为用无法访问到它。

* 但是最好再写一句data[size]=null 具体原因需要了解java的垃圾回收机制

*

* @param index

* @return

*/

publicTremove(intindex) {

if(index<0||index>=size) {

thrownewIllegalArgumentException("Remove failed.Require index >=0 and index < size");

       }

​

Tret=data[index];

for(inti=index;i<size-1;i++) {

data[i]=data[i+1];

       }

//注意维护size

size--;

data[size]=null;

​

if(size==data.length/4&&data.length/4!=0){

    resize(data.length/2);

       }

returnret;

   }

​

/**

* 不用担心数组为空的情况，因为数组如果为空,remove方法就会抛出异常

* @return

*/

publicTremoveFirst(){

returnremove(0);

   }

​

publicTremoveLast(){

returnremove(size-1);

   }

​

/**

* 从数组中删除元素e

* @param e

*/

publicbooleanremoveElement(Te){

intindex=find(e);

if(index!=-1){

remove(index);

returntrue;

}else{

returnfalse;

       }

   }

​

/**

* 重写toString()方法

*

* @return

*/

@Override

publicStringtoString() {

StringBuilderres=newStringBuilder();

res.append(String.format("size= %d,capacity= %d\n",size,data.length));

res.append("[");

for(inti=0;i<size;i++) {

res.append(data[i]);

if(i!=size-1) {

res.append(",");

           }

       }

res.append("]");

returnres.toString();

   }

​

privatevoidresize(intnewCapacity){

T[]newData=(T[])newObject[newCapacity];

for(inti=0;i<size;i++){

newData[i]=data[i];

       }

data=newData;

   }

}

推荐

最后忍不住展示一下markdown写作软件的截图，因为它实在是太美了。