【数据结构与算法（一）】动态数组

痛定思痛。 2021-12-19 17:35 325阅读 0赞

## 时间复杂度分析 ##

*  O(1)，O(n)，O(lgn)，O(nlogn)等表示时间复杂度
 *  大O描述的是算法的运行时间和输入数据之间的关系
 *  O(n)表示时间复杂度和n成线性关系
 *  O(n)时间复杂度优于O(n\*n)，这里比较的是渐进时间复杂度，即描述的是n趋近于无穷的情况

## 动态数组 ##

*  优点是支持随机访问，能快速查询，动态数组最好用于索引有语意的地方。

#### **主体** ####

public class Array<E> { 
        //保存元素的数组
        private E[] data;
        //数组中元素的实际个数
        private int size;
    
        public Array(int capacity){ 
            //java中不支持data=new E[capacity];
            data=(E[])new Object[capacity];
            size=0;
        }
        public Array(){ 
            this(10);
        }
    }

#### **查找** ####

//查找某个具有相同内容的元素第一次出现在数组中的位置，如果没查到返回-1
        public int find(E e){ 
            for(int i=0;i<size;i++){ 
                if(data[i].equals(e))//如果是自定义的对象元素，则要重写equals()
                    return i;
            }
            return -1;
        }
    
        //查找具有相同内容的元素的所有位置，返回一个数组，数组第一个元素保存查找到元素的个数
        public int[] findAll(E e) { 
            int[] ind = new int[size + 1];
            int flag = 1;
            for (int i = 0; i < size; i++) { 
                if (data[i].equals(e)) { 
                    ind[flag++] = i;
                }
            }
            //没有查找到任何具有相同内容的元素
            if (flag == 1)
                ind[0] = 0;
            else
                ind[0] = flag - 1;
            return ind;
        }

#### **添加** ####

public void add(int index,E e){ 
            if(index<0||index>size){ 
                throw new IllegalArgumentException("add failed,index illegal");
            }
            //如果容量不够，进行扩容
            if(size==data.length){ 
                resize(data.length*2);
            }
            for(int i=size-1;i>=index;i--){ 
                data[i+1]=data[i];
            }
            size++;
            data[index]=e;
        }
        //向数组最后添加一个元素
        public void addLast(E e){ 
            add(size,e);//复用add()，方便提供更多的接口
        }
        public void addFirst(E e){ 
            add(0,e);
        }

#### **删除** ####

//删除下标为index处的元素，并且返回该元素的引用
        public E remove(int index){ 
            //不用单独判断数组是否为空，index>=size会进行判断
            if(index<0||index>=size){ 
                throw new IllegalArgumentException("remove failed,index illegal");
            }
            E e=data[index];
            for(int i=index;i<size-1;i++){ 
                data[i]=data[i+1];
            }
            /*for(int i=index+1;i<size;i++）{ data[i-1]=data[i]; }*/
            size--;
            //此时data[size]仍指向一个对象（该对象没有作用了），该对象并不会被回收（闲散对象），应该手动让他被回收
            data[size]=null;
            /**如果容量过大，要进行缩容。为了避免扩容后马上又进行缩容（复杂度震荡） *所以当size为容量1/4时才进行缩容，data.length/2!=0是为了避免缩容成0 */
            if(size==data.length/4&&data.length/2!=0){ 
                resize(data.length/2);
            }
            return e;
        }
    
        public E removeFirst(){ 
            return remove(0);
        }
        public E removeLast(){ 
            return remove(size-1);
        }
    
        //删除某个元素，并返回是否删除成功的信息
        public boolean removeElement(E e){ 
            int index=find(e);
            if(index!=-1){ 
                remove(index);
                return true;
            }
            return false;
        }
        //删除所有和e具有相同内容的元素
        public boolean removeAllElement(E e){ 
            int[] ind=findAll(e);
            int cnt=ind[0],flag=0;//flag用来保存位置移动的多少
            if(cnt!=0){ 
                for(int i=1;i<=cnt;i++){ 
                    //remove函数中自带更新size，不能再次更新size
                    remove(ind[i]-flag);
                    flag++;
                }
                return true;
            }
            return false;
        }

#### **resize** ####

//变换容量
        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 getSize(){ 
            return size;
        }
    
        //返回数组的容量
        public int getCapacity(){ 
            return data.length;
        }
    
        //判断数组是否为空
        public boolean isEmpty(){ 
            return size==0;
        }
        //获取下标为index处的元素
        public E get(int index){ 
            if(index<0||index>=size){ 
                throw new IllegalArgumentException("Get failed,index illegal");
            }
            return data[index];
        }
        public void set(int index,E e){ 
            if(index<0||index>=size){ 
                throw new IllegalArgumentException("Set failed,index illegal");
            }
            data[index]=e;
        }
        //判断数组中是否包含某个具有相同内容的元素
        public boolean contains(E e){ 
            for(int i=0;i<size;i++){ 
                if(data[i].equals(e))
                    return true;
            }
            return false;
        }
        @Override
        public String toString(){ 
            StringBuilder res=new StringBuilder();
            res.append(String.format("Array size:%d,capacity:%d",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();
        }