數(shù)組.png

遍歷數(shù)組
····

 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);
    }

····

• 數(shù)組最大的優(yōu)點(diǎn)：快速查詢。
• 數(shù)組最好應(yīng)用于“索引有語意”的情況
• 但并非所有有語意的索引都適用于數(shù)組

制作屬于我們自己的數(shù)組類

public class Array {

    private int[] data;
    private int size;

    // 構(gòu)造函數(shù)，傳入數(shù)組的容量capacity構(gòu)造Array
    public Array(int capacity){
        data = new int[capacity];
        size = 0;
    }

    //無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
    public Array(){
        this(10);
    }

    //獲取數(shù)組中的元素個(gè)數(shù)
    public int getSize(){
        return size;
    }

    //獲取數(shù)組的容量
    public int getCapacity(){
        return data.length;
    }

    //返回?cái)?shù)組是否為空
    public  boolean isEmpty(){
        return  size == 0;
    }

    //向所有的元素后添加一個(gè)新元素
    public void addLast(int e ){
        add(size,e);
    }

    //在數(shù)組第一個(gè)位置插入元素
    public void addFirst(int e){
        add(0,e);
    }

    //在第index個(gè)位置插入一個(gè)新元素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 ++;
    }

}

• 在數(shù)組任意位置插入一個(gè)元素
  • 要將這個(gè)位置的所有元素的數(shù)據(jù)往后挪。

     //在第index個(gè)位置插入一個(gè)新元素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 ++;
    } 
  

在數(shù)組中查詢?cè)睾托薷脑?/h6>

• 增刪改查

  //獲取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;
    }

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

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

    //從數(shù)組中刪除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;
    }

    //從數(shù)組中刪除第一個(gè)元素，返回刪除的元素
    public int removeFirst(){
       return remove(0);
    }
    //從數(shù)組中刪除最后一個(gè)元素，返回刪除的元素
    public int  removeLast(){
        return remove(size-1);
    }

    //從數(shù)組中刪除元素e
    public void removeElement(int e){
        int index=find(e);
        if (index !=-1){
            remove(index);
        }
    }

但我們很多時(shí)候不一定只有int數(shù)組。所以此時(shí)需要支持泛型。只要將類型改為泛型即可

Array<E>

動(dòng)態(tài)數(shù)組

   //動(dòng)態(tài)擴(kuò)容
    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

時(shí)間復(fù)雜度分析

• O(1),O(n)，O（lgn）....
• 大O描述的是算法的運(yùn)行時(shí)間和輸入數(shù)據(jù)之間的關(guān)系

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

        //這個(gè)算法是時(shí)間復(fù)雜度為O(n);
        //n是nums中的元素個(gè)數(shù)
        //算法和n呈線性關(guān)系

    }

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

  • 忽略常數(shù)，實(shí)際時(shí)間T=c1*n+c2
    • c1:對(duì)每個(gè)數(shù)操作花費(fèi)的時(shí)間
    • c2:開辟空間，return 數(shù)據(jù)等之類的時(shí)間就是c2
    • O(n) 漸進(jìn)時(shí)間復(fù)雜度
    • O(n2) 描述n趨近于無窮的情況

• 高階算法的常數(shù)比較低，可能速度快于低階算法。
  無論歸并排序 還是快速排序 都可以比較小的數(shù)組 使用插入排序優(yōu)化?？梢蕴嵘?0%的性能。 插入排序算法的常數(shù)比歸并算法 和快速算法的常數(shù)要小的。

分析動(dòng)態(tài)數(shù)組的時(shí)間復(fù)雜度

• 添加操作 O(n)
  • addLast(e) O(1) 常數(shù)時(shí)間
  • addFirst(e) O(n)
  • add(index,e) 算時(shí)間復(fù)雜度的期望。用概率論知識(shí)。 O(n/2)=O(n)
• 刪除操作 O(n)
  • removeLast(e) O(1) 常數(shù)時(shí)間
  • removeFirst(e) O(n)
  • remove(index,e) 算時(shí)間復(fù)雜度的期望。用概率論知識(shí)。 O(n/2)=O(n)
• 修改操作
  set(index,e) O(1) 支持隨機(jī)訪問
• 查找操作
  • get(Index) O(1)
  • contains(e) O(n)
  • find(e) O(n)

####### resize 的復(fù)雜度分析
假設(shè) 容量=n，n+1次addLast,觸發(fā)resize,總共進(jìn)行2n+1次基本操作，平均每次操作addLast操作，進(jìn)行2次基本操作 （均攤復(fù)雜度）

復(fù)雜度震蕩

當(dāng)我們 同時(shí)addLast 和removeLast操作
當(dāng)容量為n 時(shí)， 添加第n+1個(gè)元素是 會(huì)擴(kuò)容 調(diào)用resize.此后又刪除一個(gè)元素 調(diào)用縮容方法。
出現(xiàn)問題的原因：removeLast時(shí)resize 過于周幾
解決方法：Lazy
當(dāng)size == 容量/4時(shí)，容量才減半