不要小瞧數組

来源:https://www.cnblogs.com/mengd/archive/2019/09/12/11515206.html
-Advertisement-
Play Games

一、使用java中的數組 數組:把數據碼成一排進行存放 在元素前面添加一個新元素 四、數組中查詢元素和修改元素 還是在上面的類中寫方法,這裡重寫toString方法,用於查詢元素 把前面寫的功能進行測試 說明還是成功的,由於int類型太單調,之後都將使用泛型來進行操作 七、動態數組 由於數組是由限制 ...


一、使用java中的數組

數組:把數據碼成一排進行存放

public class array {

    public static void main(String[] args ){

        //定義數組指定長度
        int[] arr = new int[10];
        for (int i = 0; i<arr.length; i++)
            arr[i] = i;

        //
        int[] scores = new int[]{100,99,66};
        for (int i = 0; i<scores.length; i++)
            System.out.println(scores[i]);

        // 數組可遍歷
        scores[0] = 98;
        for (int score: scores)
            System.out.println(score);

    }
}

二、二次封裝屬於我們自己的數組

數組最大的優點:快速查詢 score[2]

數組最好應用於“索引有語意”的情況

但並非所有有語意的索引都適合用於數組,例如身份證號

數組也可以處理“索引沒有語意”的情況,這裡主要處理“索引沒有語義”的情況數組的使用

public class array {

    private int[] data;
    private int size;

    // 構造函數,傳入數組的容量capacity構造array
    public array(int capacity){
        data = new int[capacity];
        size = 0;
    }

    // 無參數的構造函數,預設數組容量capaciay=10
    public array(){
        this(10);
    }

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

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

    // 判斷數組是否為空
    public boolean isEmpty(){
        return size == 0;
    }

}

三、向數組添加元素

向數組末尾添加元素,還是在上面的類中添加方法

   // 向所有元素後添加一個新元素
    public void addList(int e){

        // 如果元素的個數等於數組的容量,那麼拋出異常
        if (size == data.length)
            throw new IllegalArgumentException("AddLast failed. array is full");
        data[size] =  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. array is full");
        }

        for (int i = size - 1; i >= index; i--){
            data[i+1] = data[i];
        }

        data[index] = e;
        size++;

    }

在元素前面添加一個新元素

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

四、數組中查詢元素和修改元素

還是在上面的類中寫方法,這裡重寫toString方法,用於查詢元素

 @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("array: 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();
    }

獲取元素以及修改元素

  // 獲取index索引位置的元素
    int get(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("GET failed. array is full");
        return data[index];
    }


    // 修改index索引位置的元素e
    void set (int index,int e){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("set failed. array is full");
        data[index] = e;
    }

把前面寫的功能進行測試

public class Main {

    public static void main(String[] args ){

        array arr = new array(20);
        for (int i = 0 ; i < 10 ; i++){
            arr.addList(i);
        }

        System.out.println(arr);

        // 索引為1的位置添加100
        arr.add(1,100);
        System.out.println(arr);

        // 開始添加-1
        arr.addFirst(-1);
        System.out.println(arr);

    }
}

// 列印結果
array: size = 10 , capacity = 20
[0,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[0,100,1,2,3,4,5,6,7,8,9]
array: size = 12 , capacity = 20
[-1,0,100,1,2,3,4,5,6,7,8,9]

五、包含,搜索和刪除

還是在上面的類中寫方法,包含

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

搜索

 // 查找數組中元素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("Remove failed");

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

進行測試

public class Main {

    public static void main(String[] args ){

        array arr = new array(20);
        for (int i = 0 ; i < 10 ; i++){
            arr.addList(i);
        }

        System.out.println(arr);

        arr.add(1,100);
        System.out.println(arr);

        arr.addFirst(-1);
        System.out.println(arr);


        arr.remove(2);
        System.out.println(arr);

        arr.removeElement(4);
        System.out.println(arr);

        arr.removeFirst();
        arr.removeLast();
        System.out.println(arr);
    }
}

array: size = 10 , capacity = 20
[0,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[0,100,1,2,3,4,5,6,7,8,9]
array: size = 12 , capacity = 20
[-1,0,100,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[-1,0,1,2,3,4,5,6,7,8,9]
array: size = 10 , capacity = 20
[-1,0,1,2,3,5,6,7,8,9]
array: size = 8 , capacity = 20
[0,1,2,3,5,6,7,8]

基本功能已經實現,但是還是有很多需要完善的地方。

六、使用泛型

  1. 讓我們的數據結構可以放置任何的數據類型
  2. 不可以是基本數據類型,只能是類對象:boolean、byte、chat、short、int、long、float、double
  3. 每個基本數據類型都有對應的包裝類:Boolean、Byte、Chat、Short、Int、Long、Float、Double
  4. 下麵還是針對上面的進行修改,由於使用了泛型,這裡將array類全部放在這裡方便大家觀看
public class array<E> {

    // 數據類型由之前的int改成現在的
    private E[] data;
    private int size;


    // 構造函數,傳入數組的容量capacity構造array
    // 這裡使用了強制類型轉化
    public array(int capacity){
        data = (E[]) new Object[capacity];
        size = 0;
    }

    // 無參數的構造函數,預設數組容量capaciay=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(E e){

        // 如果元素的個數等於數組的容量,那麼拋出異常
        if (size == data.length)
            throw new IllegalArgumentException("AddLast failed. array is full");
        data[size] =  e;
        size++;

    }


    // 在所有元素前添加一個新元素,轉入參數類型改變
    public void addFirst(E e){
        add(0,e);
    }

    // 在第index個位置插入一個新元素e,轉入參數類型改變
    public void add(int index,E e){

        if (size == data.length)
            throw new IllegalArgumentException("Add failed. array is full");

        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. array is full");
        }

        for (int i = size - 1; i >= index; i--){
            data[i+1] = data[i];
        }

        data[index] = e;
        size++;


    }



    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("array: 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();

    }


    // 獲取index索引位置的元素,返回類型改變
    E get(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("GET failed. array is full");
        return data[index];
    }


    // 修改index索引位置的元素e,轉入參數類型改變
    void set (int index,E e){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("set failed. array is full");
        data[index] = e;
    }


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


    // 查找數組中元素e所在的索引,如果元素不存在,返回-1,轉入參數類型改變
    public int find(E e){
        for (int i = 0 ; i < size ; i++){
            if (data[i] .equals(e) ){
                return i;
            }
        }
        return -1;
    }

    // 從數組中刪除index位置的元素,返回刪除的元素,返回類型改變
    public E remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed");

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


    // 從數組中刪除第一個元素,返回刪除的元素
    public E removeFirst(){
        return remove(0);
    }
    // 從數組中刪除最後一個元素,返回刪除的元素
    public E removeLast(){
        return remove(size - 1);
    }

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

}

為了進行測試,從新建一個Student類來進行測試,這樣就可以使用任意類型的數據

public class Student {

    private String name;
    private int score;

    public Student(String studentName, int studentScore){
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString() {
        return String.format("Student(name: %s , score: %d)\n",name,score);
    }

    public static void main(String[] args){

        // 使用泛型
        array<Student> arr = new array<>();
        arr.addLast(new Student("Alice",100));
        arr.addLast(new Student("Bob",88));
        arr.addLast(new Student("Char",66));

        System.out.println(arr);
    }

}
public class Student {

    private String name;
    private int score;

    public Student(String studentName, int studentScore){
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString() {
        return String.format("Student(name: %s , score: %d)\n",name,score);
    }

    public static void main(String[] args){

        // 使用泛型
        array<Student> arr = new array<>();
        arr.addLast(new Student("Alice",100));
        arr.addLast(new Student("Bob",88));
        arr.addLast(new Student("Char",66));

        System.out.println(arr);
    }


}

array: size = 3 , capacity = 10
[Student(name: Alice , score: 100)
,Student(name: Bob , score: 88)
,Student(name: Char , score: 66)
]

說明還是成功的,由於int類型太單調,之後都將使用泛型來進行操作

七、動態數組

由於數組是由限制的,在用戶不知道數據的個數的時候,容易拋出異常,這個時候就要使用動態數組,而不用再考慮數據的個數

具體的實現,還是在array類中

    // 動態數組
    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 void add(int index,E e){

        // 如果數組已經滿了
        if (size == data.length)
//            throw new IllegalArgumentException("Add failed. array is full");
            // 調用動態數組,擴容到之前容量的二倍
            resize(2 * data.length);


        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. array is full");
        }

        for (int i = size - 1; i >= index; i--){
            data[i+1] = data[i];
        }

        data[index] = e;
        size++;


    }

把刪除元素的方法也進行改寫

  public E remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed");

        E ret = data[index];
        for (int i = index + 1 ; i < size ; i++)
            data [ i - 1] = data[i];
        size --;
        // data[size] = null;    // loitering objects

        // 如果數組中剩餘的數量是數組長度的二倍,那麼就把數組的長度減半
        if (size == data.length / 2)
            resize(data.length / 2);

        return ret;
    }

進行測試

public class Main {

    public static void main(String[] args ){

        // int類型的包裝類
        array<Integer> arr = new array<>(5);

        for (int i = 0 ; i < 5 ; i++){
            arr.addLast(i);
        }

        System.out.println(arr);

        arr.add(1,100);
        System.out.println(arr);

        arr.addFirst(-1);
        System.out.println(arr);


        arr.remove(2);
        System.out.println(arr);

        arr.removeElement(4);
        System.out.println(arr);

        arr.removeFirst();
        arr.removeLast();
        System.out.println(arr);
    }
}

array: size = 5 , capacity = 5
[0,1,2,3,4]
當數據多的時候,自動擴容的之前的兩倍
array: size = 6 , capacity = 10
[0,100,1,2,3,4]
array: size = 7 , capacity = 10
[-1,0,100,1,2,3,4]
array: size = 6 , capacity = 10
[-1,0,1,2,3,4]
當數據少的時候,自動縮少兩倍
array: size = 5 , capacity = 5
[-1,0,1,2,3]
array: size = 3 , capacity = 5
[0,1,2]

這樣就基本實現了動態的數組

八、簡單的時間複雜度分析

  1. O(1),O(n),O(lgn),O(nlogn),O(n^2)
  2. 大O描述的是演算法的運行時間和輸入數據之間的關係
public static int sum(int[] nums){
    int sun = 0;
    for(int num: nums) sum += num;
    return sum;
}

這裡演算法是O(n),這裡n是nums中元素的個數

也就是說這個演算法運行的時間的多少和這裡的nums中元素的個數呈線性關係,也就是nums中的個數越多時間就越多

  1. 為什麼要用大O,叫做O(n)?忽略常數,實際時間(線性)
    $$
    T = c1*n + c2
    $$

具體分析演算法的時候就直接忽略常數,漸進時間複雜度,描述n趨近於無窮的情況

T = 2*n + 2 O(n)
T = 2000*n + 1000 O(n)
T = nn1 + 0 O(n^2)
T = 2nn + 300*n + 10 O(n^2)

其中n的冪數越大性能越差

分析動態數組的時間複雜度

向數組頭添加元素的時候,要把數組中的每一個元素往後面移動,所以是O(n),整體來看,通常做最壞的打算,也是O(n),添加的還有註意resize方法

添加操作 O(n)
addLast(e) O(1)
addFirst(e) O(n)
add(index,e) O(n/2) = O(n)
resize O(n)

刪除操作和上面的一樣,也是做最壞的打算,也是O(n),刪除時還要註意resize方法

刪除操作 O(n)
removeLast(e) O(1)
removeFirst(e) O(n)
remove(index,e) O(n/2) = O(n)

修改操作,這個是最簡單的,O(1)

修改操作 O(1)
set(index,e) O(1)

查找操作,也是O(n)

查找操作 O(n)
get(index) O(1)
contains(e) O(n)
find(e) O(n)

總結

O(n)
O(n)
已知索引O(1),未知索引O(n)
已知索引O(1),未知索引O(n)

註意:對於增和刪,如果只對最後一個元素操作依然是O(n)?,因為resize方法?

九、均攤複雜度和防止複雜度的震蕩

  1. resize的複雜度分析

從最壞的方面來看,addLast(e)的複雜度是O(1),如果此時數組容量不夠需要擴容的時候就要調用resize方法,但是resize方法的複雜度是O(n),所以綜合來說addLast(e)的複雜度是O(n),但是也不是每一次添加就會擴容,所以用最壞的來分析有點不合理,這裡用到下麵的知識了

假設當前的capacity = 8 ,並且每一次添加操作都使用addLast
$$
1+1+1+1+1+1+1+1+8+1
$$
9次addLast操作,觸發resize,總共進行了17次的基本操作,9次添加,8次轉移,

平均來說也就是每次addLast操作,進行了大約兩次基本操作

假設capacity = n,n+1次addLast,觸發resize,總共進行2n+1次基本操作

平均,每次addLast操作,進行2次基本操作

這樣均攤計算,時間複雜程度是O(1)

所以在這個例子中,均攤計算,比計算最壞情況有意義

  1. 均攤複雜度

addLast的均攤複雜度是O(1)

同理,removeLast的均攤複雜度也是O(1)

  1. 複雜度的震蕩

但是,我們同時來看addLast和removeLast操作

當capacity = n時,調用addLast,這裡進行擴容,複雜度O(n),然後執行removeLast,進行縮容,複雜度也是O(n),如此迴圈,複雜度就一直是O(n)了

出現問題的原因:removeLast是resize過於著急(Eager),不必一下子就縮容

解決方案:Lazy,當數據是總長度的1/4時進行縮容,縮容還是變回原來的一半

當size == capacity /4 時,才將capacity減半

通過這樣的方法,就解決了複雜度震蕩的問題

下麵用代碼實現,還是在array類中修改,把remove方法改寫就可以了,

public E remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed");

        E ret = data[index];
        for (int i = index + 1 ; i < size ; i++)
            data [ i - 1] = data[i];
        size --;
        // data[size] = null;    // loitering objects

        // 這裡等於1/4的才進行縮容,但是還要註意長度除於2不能等於0
        if (size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);

        return ret;
    }


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 一、序列化組件 簡單使用 開發我們的Web API的第一件事是為我們的Web API提供一種將代碼片段實例序列化和反序列化為諸如 之類的表示形式的方式。我們可以通過聲明與Django forms非常相似的序列化器(serializers)來實現。 models部分: views部分: ModelSe ...
  • 之前通過hook技術實現了微信pc端發送消息功能,如果在結合圖靈機器人就能實現微信聊天機器人。 代碼下載:http://blog.yshizi.cn/131.html 邏輯如下: ![捕獲.jpg][1] 下麵我簡單介紹一下步驟。 1. 首先,你需要下載我的微信助手,下載地址請參考我的博客文章: [ ...
  • arraylist源碼分析 1.數組介紹 數組是數據結構中很基本的結構,很多編程語言都內置數組,類似於數據結構中的線性表 在java中當創建數組時會在記憶體中劃分出一塊連續的記憶體,然後當有數據進入的時候會將數據按順序的存儲在這塊連續的記憶體中。當需要讀取數組中的數據時,需要提供數組中的索引,然後數組根據 ...
  • 1.配置模板文件 2.配置mysql資料庫 創建資料庫 配置settings 方法一:直接在settings.py文件中添加資料庫配置信息 方法二:將資料庫配置信息存到一個文件,在settings文件中將其引入。(推薦) 新建資料庫配置文件db.cnf(名字隨意) db.cnf文件內容: 在sett ...
  • 對應的圖: 圖的結構Ref:https://wenku.baidu.com/view/9fdeaa3c2b160b4e767fcff7.html 小結: 最重要的是記住:在搜索過程中,若節點i對應的distance[i]發生改變,那麼對其任意一個鄰居節點j,對應的distance[j]都要重新計算, ...
  • 1、直接在新建工程的時候選擇CUDA,這樣的工程既能編譯C++也能編譯CU 2、在已有的C++工程上添加CUDA編譯環境 右鍵工程-->生成依賴項-->生成自定義-->勾選CUDA 9.0 這時右鍵工程屬性,發現多了兩個關於CUDA的屬性 點擊CUDA C/C++下的Common,將預設的32-bi ...
  • 爬取b站彈幕並不困難。要得到up主所有視頻彈幕,我們首先進入up主視頻頁面,即https://space.bilibili.com/id號/video這個頁面。按F12打開開發者菜單,刷新一下,在network的xhr文件中有一個getSubmitVideo文件,這個文件里就有我們需要的視頻av號了 ...
  • 一.Java創建線程的三種方式 Java中創建線程主要有三種方式: 1.繼承Thread類 2.實現Runnable介面 3.使用Callable和Future 1.繼承Thead類創建線程 (1)繼承Thread類並重寫run方法 (2)創建線程對象 (3)調用該線程對象的start()方法來啟動 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...