第二章 不要小瞧数组

数组.png

遍历数组
····

 int[] arr = new int[10];
    for (int i=0;i<arr.length;i++){
        arr[i]=i;
    }
    int [] scores = new int[]{100,90,66};
    for (int i=0;i<scores.length;i++){
    }
    for (int score:scores){
        System.out.println(score);
    }

····

• 数组最大的优点：快速查询。
• 数组最好应用于“索引有语意”的情况
• 但并非所有有语意的索引都适用于数组

制作属于我们自己的数组类

public class Array {

    private int[] data;
    private int size;

    // 构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data = new int[capacity];
        size = 0;
    }

    //无参数的构造函数，默认数组的容量capacity=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 ){
        add(size,e);
    }

    //在数组第一个位置插入元素
    public void addFirst(int e){
        add(0,e);
    }

    //在第index个位置插入一个新元素e
    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.Require index>=0 and <=size.lenght");
        }
        for (int i=size-1;i>=index;i--){
            data[i+1]=data[i];
        }
        data[index]=e;
        size ++;
    }

}

• 在数组任意位置插入一个元素
  • 要将这个位置的所有元素的数据往后挪。

     //在第index个位置插入一个新元素e
    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.Require index>=0 and <=size.lenght");
        }
        for (int i=size-1;i>=index;i--){
            data[i+1]=data[i];
        }
        data[index]=e;
        size ++;
    } 
  

在数组中查询元素和修改元素

• 增删改查

  //获取index索引位置的元素
    int get (int index){
        if (index<0|| index>=size){
            throw new IllegalArgumentException("Get failed.Index is illegall.");
        }
        return data[index];
    }
    //修过index索引位置的元素为e
    void set(int index,int e ){
        if (index<0|| index>=size){
            throw new IllegalArgumentException("Get failed.Index is illegall.");
        }
         data[index]=e;
    }

    //查找数组是否有元素e
    public boolean contains(int e){
        for (int i =0;i<size;i++){
            if (data[i] ==e){
                return true;
            }
        }
        return false;
    }

    //查找数组中元素e所在的索引，如果不存在元素e,则返回-1
    public int find(int e){
        for (int i =0;i<size;i++){
            if (data[i] ==e){
                return i;
            }
        }
        return -1;
    }

    //从数组中删除index位置的元素，返回删除的元素
    public int  remove(int index){
        if (index<0|| index>=size){
            throw new IllegalArgumentException("Get failed.Index is illegall.");
        }
        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);
    }

    //从数组中删除元素e
    public void removeElement(int e){
        int index=find(e);
        if (index !=-1){
            remove(index);
        }
    }

但我们很多时候不一定只有int数组。所以此时需要支持泛型。只要将类型改为泛型即可

Array<E>

动态数组

   //动态扩容
    private void resize(int newCapacity){
        E[] newData=(E[])new Object[newCapacity];
        for (int i =0;i<size;i++){
            newData[i]=data[i];
        }
        data=newData;
    }

• 自定义Array代码地址：https://github.com/FoxconnPeter/PeterBlog/blob/master/%E8%87%AA%E5%AE%9A%E4%B9%89Array.md

时间复杂度分析

• O(1),O(n)，O（lgn）....
• 大O描述的是算法的运行时间和输入数据之间的关系

    public static int sum(int[] nums){
        int sum=0;
        for (int num:nums) sum += num;
        return sum;

        //这个算法是时间复杂度为O(n);
        //n是nums中的元素个数
        //算法和n呈线性关系

    }

• 为什么要用大O，叫做O(n)?

  • 忽略常数，实际时间T=c1*n+c2
    • c1:对每个数操作花费的时间
    • c2:开辟空间，return 数据等之类的时间就是c2
    • O(n) 渐进时间复杂度
    • O(n²) 描述n趋近于无穷的情况

• 高阶算法的常数比较低，可能速度快于低阶算法。
  无论归并排序 还是快速排序 都可以比较小的数组 使用插入排序优化。可以提升10%的性能。 插入排序算法的常数比归并算法 和快速算法的常数要小的。

分析动态数组的时间复杂度

• 添加操作 O(n)
  • addLast(e) O(1) 常数时间
  • addFirst(e) O(n)
  • add(index,e) 算时间复杂度的期望。用概率论知识。 O(n/2)=O(n)
• 删除操作 O(n)
  • removeLast(e) O(1) 常数时间
  • removeFirst(e) O(n)
  • remove(index,e) 算时间复杂度的期望。用概率论知识。 O(n/2)=O(n)
• 修改操作
  set(index,e) O(1) 支持随机访问
• 查找操作
  • get(Index) O(1)
  • contains(e) O(n)
  • find(e) O(n)

####### resize 的复杂度分析
假设 容量=n，n+1次addLast,触发resize,总共进行2n+1次基本操作，平均每次操作addLast操作，进行2次基本操作 （均摊复杂度）

复杂度震荡

当我们 同时addLast 和removeLast操作
当容量为n 时， 添加第n+1个元素是 会扩容 调用resize.此后又删除一个元素 调用缩容方法。
出现问题的原因：removeLast时resize 过于周几
解决方法：Lazy
当size == 容量/4时，容量才减半