Skip to content

Latest commit

 

History

History
308 lines (269 loc) · 7.54 KB

00数组.md

File metadata and controls

308 lines (269 loc) · 7.54 KB

数组

二次封装属于自己的数组

准备工作：

/**
 * 二次封装属于我们自己的数组的准备工作
 */
public class Array {
    private int[] data;
    private int size;

    public Array(int capacity){
        data=new int[capacity];
        size=0;
    }

    //无参构造函数，默认数组的容量是10
    public Array(){
        this(10);
    }

    public int getSize(){
        return size;
    }

    public int getCapacity(){
        return data.length;
    }

    public boolean isEmpty(){
        return size==0;
    }
}

向数组中添加元素

//在所有元素后添加新元素
public void addLast(int e) {
    //要先判断是否有空间来容纳新元素
    /*if(size==data.length){
        throw new IllegalArgumentException("AddLast failed,array is full");
    }
    data[size]=e;
    size++;*/
    add(size,e);
}

//在所有元素前添加新元素
public void addFirst(int e){
    add(0,e);
}

//在index位置插入元素
public void add(int index,int e){
    if(size==data.length){
        throw new IllegalArgumentException("Add failed,array is full");
    }
    if(index<0 || index>size){
        throw new IllegalArgumentException("Add Failed,0<=index<=size is required");
    }
    //index位置后的元素向右移动
    for(int i=size;i>index;i--){
        data[i]=data[i-1];
    }
    data[index]=e;
    size++;
}

在数组中查询和修改元素

//获取index位置的元素
public int get(int index){
    if(index<0 || index>=size){
        throw new IllegalArgumentException("Get failed,index is illegal");
    }
    return data[index];
}

//设置index位置元素值为e
public void set(int index,int e){
    if(index<0 || index>=size){
        throw new IllegalArgumentException("Get failed,index is illegal");
    }
    data[index]=e;
}

@Override
public String toString(){
    StringBuilder builder=new StringBuilder();
    builder.append(String.format("Array size=%d,capacity=%d\n",size,data.length));
    builder.append("[");
    for(int i=0;i<size;i++){
        builder.append(data[i]);
        if(i!=size-1){
            builder.append(", ");
        }
    }
    builder.append("]");
    return builder.toString();
}

数组中的包含、搜索和删除元素

//查找数组中是否有元素e,有就返回下标，没有就返回-1
public boolean contains(int e){
    for(int i=0;i<size;i++){
        if(data[i]==e){
            return true;
        }
    }
    return false;
}
//查找数组中元素e所在索引
public int find(int e){
    for(int i=0;i<size;i++){
        if(data[i]==e){
            return i;
        }
    }
    return -1;
}
//删除指定位置元素
public int remove(int index){
    if(size==0){
        throw new IllegalArgumentException("Remove failed,array is empty");
    }
    if(index<0 || index>=size){
        throw new IllegalArgumentException("Remove failed,index is illegal");
    }
    int ret=data[index];
    for(int i=index+1;i<size;i++){
        data[i-1]=data[i];
    }
    size--;
    return ret;
}

public int removeFirst(){
    return remove(0);
}

public int removeLast(){
    return remove(size-1);
}

public void removeElement(int e){
    int index=find(e);
    if(index!=-1){
        remove(index);
    }
}

动态数组

调整数组大小

  • 准备一个新数组，长度是原来数组的2倍
  • 将原来数组中的元素复制到新数组中
  • 将data指向newData,完成扩容
  • 完成扩容，capacity是原来的2倍,size不变，数组中数据不变
//动态调整数组大小
private void resize(int newCapacity){
    E[] newData=(E[])new Object[newCapacity];
    for(int i=0;i<size;i++){
        newData[i]=data[i];
    }
    data=newData;
}

动态数组中的插入和删除

//删除指定位置元素
public int remove(int index){
    /*if(size==0){
        throw new IllegalArgumentException("Remove failed,array is empty");
    }*/
    if(size==data.length/2){
        resize(data.length/2);
    }
    if(index<0 || index>=size){
        throw new IllegalArgumentException("Remove failed,index is illegal");
    }
    E ret=data[index];
    for(int i=index+1;i<size;i++){
        data[i-1]=data[i];
    }
    size--;
    data[size]=null;//loitering objects
    return ret;
}
//在index位置插入元素
public void add(int index,E e){
   /* if(size==data.length){
        throw new IllegalArgumentException("Add failed,array is full");
    }*/
    if(size==data.length){
        resize(data.length*2);
    }
    if(index<0 || index>size){
        throw new IllegalArgumentException("Add Failed,0<=index<=size is required");
    }
    //index位置后的元素向右移动
    for(int i=size;i>index;i--){
        data[i]=data[i-1];
    }
    data[index]=e;
    size++;
}

简单的时间复杂度分析

操作 时间复杂度
添加操作 平均时间复杂度：O(n)
addLast(e) O(1)
addFirst(e) O(n)
add(index) O(n)
删除操作 平均时间复杂度：O(n)
removeLast(e) O(1)
removeFirst(e) O(n)
remove(index,e) O(n)
修改操作
set(index,e) O(1)
查找操作
get(index) O(1)
contains(e) O(n)
find(e) O(n)

resize的时间复杂度分析

假设capacity=n,n+1次进行addLast操作，会触发resize, 总共进行2*n+1次基本操作。

平均情况下，每次addLast操作，进行2次基本操作。

这样均摊计算，时间复杂度是O(1)。

所以addLast的均摊复杂度是 O(1)。

同理，removeLast的均摊复杂度是O(1)。

  • 复杂度震荡：
  • 出现问题的原因：removeLast时resize过于着急。

解决方法：lazy

当 size==capacity/4 时，才将capacity减半。

//删除指定位置元素
public int remove(int index){
    /*if(size==0){
        throw new IllegalArgumentException("Remove failed,array is empty");
    }*/
   /* if(size==data.length/2){
        resize(data.length/2);
    }*/
    if(size==data.length/4 && data.length/2!=0){
        resize(data.length/2);
    }
    if(index<0 || index>=size){
        throw new IllegalArgumentException("Remove failed,index is illegal");
    }
    E ret=data[index];
    for(int i=index+1;i<size;i++){
        data[i-1]=data[i];
    }
    size--;
    //data[size]=null;//loitering objects,使用泛型时，进行此操作
    return ret;
}