1.数组基础
数组最一种存放数据的线性数据结构 ,最原始的数组是一种静态数组,需要声明数组的容量,一旦new出来数组对象大小不可改变,可以通过索引来进行数据的增删改查。我们可以通过对静态数组的二次封装来进行改进成动态数组。
*数组最大的优点:快速查询。
*数组最好用于“索引有语意”的情况。
*但并非所有有有语意的索引都适用于数组。 例如当用数组存放人员时,用身份证号来充当索引,此时能够区别人员,但身份证号太长,极大浪费内存空间得不偿失。
*数组也可以处理索引没有语意的情况。
基于静态数组实现的动态数组源码如下:
/** * 对静态数组的二次封装,改进成一个动态数组 * * @author zhangtianci */public class Array<E>{ private E[] data; //用来存放数据 private int size; //当前数组中存放数据的个数 /** * 构造方法 * * @param capacity 数组的容量 */ public Array(int capacity){ data = (E[]) new Object[capacity]; size = 0; } /** * 无参构造函数,默认数组的容量为10 */ public Array(){ this(10); } /** *获取当前数组中存放数据的个数 * *@return size of array */ public int getSize(){ return size; } /** * 获取数组的大小 * * @return capacity of array */ public int getCapacity(){ return data.length; } /** * 判断数组是否为空 * * @return true is empty,false is not */ public boolean isEmpty(){ return size == 0; } /** * 向所有元素后添加一个新元素 * * @param e a new element of array */ public void addLast(E e){ add(size, e); } /** * 向所有元素前添加一个新元素 * * @param e */ public void addFirst(E e){ add(0, e); } /** * 在index个位置插入一个元素 * * @param index * @param e */ public void add(int index, E e){ if(index < 0 || index >size){ throw new IllegalArgumentException("Add failed.Require index >= 0 and index <= size."); } if(size == data.length){ resize(2 * data.length); } for(int i = size - 1;i >= index; i--){ data[i+1] = data[i]; } data[index] = e; size++; } /** * 获取索引为index上的元素 * * @param index * @return */ public E get(int index){ if (index < 0 || index >= size){ throw new IllegalArgumentException("Get failed.Index is Illggal."); } return data[index]; } /** * 修改索引为index上的元素 * * @param index * @param e */ public void set(int index,E e){ if (index < 0 || index >= size){ throw new IllegalArgumentException("Set failed.Index is Illggal."); } data[index] = e; } /** * 查询该数组中是否存在该元素,若存在则返回true,反之false * * @param e * @return */ public boolean contains(E e){ for(int i = 0; i < size; i++){ if (data[i].equals(e)) { return true; } } return false; } /** * 查找数组中该元素的索引,若不存在则返回-1 * * @param e * @return */ public int find(E e){ for(int i = 0; i < size; i++){ if (data[i].equals(e)) { return i; } } return -1; } /** * 删除数组指定索引的元素 * * @param index * @return */ public E remove(int index){ if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed.Index is Illegal."); } E ret = data[index]; for(int i = index; i < size - 1; i++){ data[i] = data[i + 1]; } size--; data[size] = null; if(size == data.length / 4 && data.length / 2 != 0){ resize(data.length / 2); } return ret; } /** * 删除数组第一个元素 * * @return */ public E removeFirst(){ return remove(0); } /** * 删除数组最后一个元素 * * @return */ public E removeLast(){ return remove(size -1); } /** * 删除数组中的元素e * * @param e */ public void removeElement(E e){ int index = find(e); if(index != -1){ remove(index); } } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Arrry: 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(); }
/** * 当数组容量达到上限或者不足容量时,重新定义容量 * * @param newCapacity */ private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for(int i = 0;i < size; i++){ newData[i] = data[i]; } data = newData; } }
简单的时间复杂度分析
*时间复杂度一般分为 O(1),O(n),O(lg),O(nlogn),O(n^2)
*大O描述的是算法的运行时间和输入数据之间的关系
*为什么要用大O,叫做O(n)? 忽略常数,其实又叫做渐进时间复杂度,描述n趋近与无穷的情况下,所以常数几乎可以忽略。
对封装数组的时间复杂度分析
*添加操作
addLast(e) : O(1) ,但一旦达到了数组的容量进行扩容时,就需要进行resize()操作,所以在这种情况下时间复杂度也为O(n)
addFirst (e) : O(n)
addIndex(index,e) : O(n)
综上所述在最坏的情况下,添加操作的时间复杂度为O(n)
*删除操作
removeLast() : O(1),但一旦达到了数组的容量进行缩容时,就需要进行resize()操作,所以在这种情况下时间复杂度也为O(n)
removeFirst() : O(n)
remove(index) : O(n)
综上所述在最坏的情况下,添加操作的时间复杂度为O(n)
*修改操作
set(index,e) : O(1)
*查找操作
get(index) : O(1)
contains(e) : O(n)
find(e) : O(n)
综上:增:O(n),删:O(n),改:当已知索引时O(1),当不知索引时即要首先进行一次遍历查到该元素再进行修改则为O(n),查:已知索引O(1),未知索引O(n)
所以,当使用数组时最好使用当数组的索引具有语意的情况,那么当进行查找和修改时则会在性能上有非常大的优势,对于增加和删除时最好使用 addLast()和 removeLast() 操作,因为在这两种操作的时间复杂度都为O(1)。
risize的时间复杂度分析 O(n)
从均摊时间复杂度来讲,在capacity为n时addLast()和remove()操作平均下来为(2n+1)/(n+1)=2次操作,所以从这个角度来看addLast()和removeLast()的复杂度为
O(1)。
复杂震荡度
但是,当我们操作addLast()和removeLast()过于着急时,就会出现震荡复杂度这种情况
解决方案:Lazy,正如以上代码中removeLast()方法中当缩容时,当size==capacity/4时,才将capacity的容量减半。
扩容时