咱也不知道咋想的，周末的的时候闲来没事，因为看到一道数组的面试题，我就跟数组杠上了，问题也不大，就是一个数组重写的问题，我不知道大家有没有遇到过类似的问题，在日常的开发环境中，反正我是没遇到过，正常的开发就行，可能是因为我公司业务的原因吧，哈哈哈哈
但是，我个人的爱好就是会看一些面试题，去考察自己的知识点掌握情况，以及和市场的动态，建议大家也可以这样试一下，保持自己的竞争力，所以，在看到这道面试题之后，我就想去试一下，然后就有了下面的代码详解
看正式代码之前，关注我给我点动力吧，让我能更好的往下创作，个人公众号：Java 架构师联盟，每日更新技术好文
嘿嘿嘿，好了，说正事
int 类型数组
public class Main { public static void main(String[] args) { Array score=new Array(10); for(int i=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()); }}
复制代码
修改为泛型
public class Array<T> { private T[] data; private int size; public Array() { this(10); } public Array(int capacity) { //java本身不支持直接new 一个泛型数组，所以用以下方法实现 data = (T[])new Object[capacity]; size = 0; } public int getSize() { return size; } public int getCapacity() { return data.length; } public boolean isEmpty() { return size == 0; } /** * 向数组末尾添加元素 * * @param e */ public void addLast(T e) { add(size, e); } /** * 向数组开头添加元素 * * @param e */ public void addFirst(T e) { add(0, e); } /** * 向任意合法位置添加元素 * * @param index * @param e */ public void add(int index, T e) { if (size == data.length) { throw new IllegalArgumentException("Add is fail.Array is full"); } if (index < 0 || index > size) { throw new IllegalArgumentException("Add is fail.Require index >= 0 and index < size"); } for (int i = size; i > index; i--) { data[i] = data[i - 1]; } data[index] = e; size++; } /** * 获取索引位置的元素 * 通过这种封装，用户无法查询未使用的空间，保证了数据的安全性。 * * @param index * @return */ public T get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get is failed.Index is illegal"); } return data[index]; } /** * 修改索引位置的元素 * * @param index * @param e */ public void set(int index, T e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Set is failed.Index is illegal"); } data[index] = e; } /** * 数组中是否包含某个元素 * * @param e * @return */ public boolean contains(T e) { for (int i = 0; i < size; i++) { //注意值的比较应修改为equals方法 if (data[i].equals(e)) { return true; } } return false; } /** * 查询数组中某个元素的索引 * * @param e * @return 没有该元素则返回-1 */ public int find(T e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return i; } } return -1; } /** * 删除index位置的元素，并且返回该元素 * 不用担心删除后原来size位置的元素，因为用无法访问到它。 * 但是最好再写一句data[size]=null 具体原因需要了解java的垃圾回收机制 * * @param index * @return */ public T remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed.Require index >=0 and index < size"); } T ret = data[index]; for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } //注意维护size size--; data[size]=null; return ret; } /** * 不用担心数组为空的情况，因为数组如果为空,remove方法就会抛出异常 * @return */ public T removeFirst(){ return remove(0); } public T removeLast(){ return remove(size-1); } /** * 从数组中删除元素e * @param e */ public boolean removeElement(T e){ int index=find(e); if(index!=-1){ remove(index); return true; }else{ return false; } } /** * 重写toString()方法 * * @return */ @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("size= %d,capacity= %d\n", size, data.length)); res.append("["); for (int i = 0; i < size; i++) { res.append(data[i]); if (i != size - 1) { res.append(","); } } res.append("]"); return res.toString(); }}
复制代码
增加数组大小
前面当我们向数组中添加元素时，如果 index==size，表示数组已满。
if (size == data.length) { throw new IllegalArgumentException("Add is fail.Array is full");}
复制代码
现在可以考虑这样做，依然判断插入位置是否合法，但是当 size 等于数组长度时，自动为数组扩容——resize(2*data.length); 之所以是扩为原来的 2 倍，是因为这样扩容量的大小和原来容量大小有关，既不会过小也不会过大。
private void resize(int newCapacity){ T[] newData=(T[])new Object[newCapacity]; for(int i=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，这是不合法的。
修改后的完整代码
public class Array<T> { private T[] data; private int size; public Array() { this(10); } public Array(int capacity) { //java本身不支持直接new 一个泛型数组，所以用以下方法实现 data = (T[])new Object[capacity]; size = 0; } public int getSize() { return size; } public int getCapacity() { return data.length; } public boolean isEmpty() { return size == 0; } /** * 向数组末尾添加元素 * * @param e */ public void addLast(T e) { add(size, e); } /** * 向数组开头添加元素 * * @param e */ public void addFirst(T e) { add(0, e); } /** * 向任意合法位置添加元素 * * @param index * @param e */ public void add(int index, T e) { /*if (size == data.length) { throw new IllegalArgumentException("Add is fail.Array is full"); }*/ if (index < 0 || index > size) { throw new IllegalArgumentException("Add is fail.Require index >= 0 and index < size"); } if(size == data.length){ resize(2*data.length); } for (int i = size; i > index; i--) { data[i] = data[i - 1]; } data[index] = e; size++; } /** * 获取索引位置的元素 * 通过这种封装，用户无法查询未使用的空间，保证了数据的安全性。 * * @param index * @return */ public T get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get is failed.Index is illegal"); } return data[index]; } /** * 修改索引位置的元素 * * @param index * @param e */ public void set(int index, T e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Set is failed.Index is illegal"); } data[index] = e; } /** * 数组中是否包含某个元素 * * @param e * @return */ public boolean contains(T e) { for (int i = 0; i < size; i++) { //注意值的比较应修改为equals方法 if (data[i].equals(e)) { return true; } } return false; } /** * 查询数组中某个元素的索引 * * @param e * @return 没有该元素则返回-1 */ public int find(T e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return i; } } return -1; } /** * 删除index位置的元素，并且返回该元素 * 不用担心删除后原来size位置的元素，因为用无法访问到它。 * 但是最好再写一句data[size]=null 具体原因需要了解java的垃圾回收机制 * * @param index * @return */ public T remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed.Require index >=0 and index < size"); } T ret = data[index]; for (int i = 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); } return ret; } /** * 不用担心数组为空的情况，因为数组如果为空,remove方法就会抛出异常 * @return */ public T removeFirst(){ return remove(0); } public T removeLast(){ return remove(size-1); } /** * 从数组中删除元素e * @param e */ public boolean removeElement(T e){ int index=find(e); if(index!=-1){ remove(index); return true; }else{ return false; } } /** * 重写toString()方法 * * @return */ @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("size= %d,capacity= %d\n", size, data.length)); res.append("["); for (int i = 0; i < size; i++) { res.append(data[i]); if (i != size - 1) { res.append(","); } } res.append("]"); return res.toString(); } private void resize(int newCapacity){ T[] newData=(T[])new Object[newCapacity]; for(int i=0;i<size;i++){ newData[i]=data[i]; } data=newData; }}
复制代码
推荐
最后忍不住展示一下 markdown 写作软件的截图，因为它实在是太美了。
评论