此篇文章是用來紀錄學習超圖解!一次搞懂演算法|入門篇 實作項目的部分與代碼分析。

思路

  1. 初始化一個空的陣列,用來存放資料。
  2. 設定最後位數作為判斷依據。
  3. 新增藉由 index 添加 value。<add_by_index>
  4. 新增直接添加 value。 <add_by_value>
  5. 新增藉由 index 刪除 value。 <remove_by_index>
  6. 新增直接刪除 value。 <remove_by_value>
  7. 新增藉由 index 搜尋 value。 <search_by_index>
  8. 新增藉由 value 搜尋 index。 <search_by_value>

實作新增

初始化

public class ArrayImp2 {
    private Integer[] array;
    private Integer i_end;

    public ArrayImp2(int size) {
        array = new Integer[size];
        i_end = -1;
    }
}

測試情境1: add_by_index

public static void main(String[] args) {
    ArrayImp2 mary = new ArrayImp2(5);

    mary.add_by_index(0, 10);
    mary.add_by_index(1, 20);
    mary.add_by_index(2, 30);
    mary.add_by_index(3, 40);
    mary.add_by_index(4, 50);

    // expand the array
    mary.add_by_index(5, 60);
    mary.add_by_index(6, 70);

    System.out.println();
}

add_by_index

public void add_by_index(int i_add, int value) {
    // 如果插入在中間必須先將原有內容往後移除空間給要新增內容
    for(int i = i_end; i >= i_add; i--) {
        array[i+1] = array[i];
        array[i] = null; // 清空
    }
    
    array[i_add] = value; // 放入
    i_end++; // 添加最大內容數
}

這樣會有兩個例外狀況:

  1. 如果輸入超出初始化陣列空間會報錯,需要進行擴展空間。
  2. 如果輸入超出範圍 index 也會報錯。

例外處理1

public void add_by_index(int i_add, int value) {
    if (i_end + 1 == array.length) expand_space();

}

private void expand_space() {
    // 創造新陣列並擴展空間*2
    Integer[] new_array = new Integer[array.length * 2];
    
    //依序將原有內容搬入新陣列
    for (int i = 0; i < array.length; i++) {
        new_array[i] = array[i];
    }
    
    // 設定新陣列取代
    this.array = new_array;
}

例外處理2

public void add_by_index(int i_add, int value) {
    // ...
    // 大於最後一位 + 1, 4+1=5, i_add=6 > 5 中間少一位<這邊需求連續性>
    // 小於第一位 0
    if (i_add > i_end + 1 || i_add < 0) return;
}

測試情境2: add_by_value

public static void main(String[] args) {
    ArrayImp2 mary = new ArrayImp2(5);

    mary.add_by_value(10);
    mary.add_by_value(20);
    mary.add_by_value(30);
    mary.add_by_value(40);
    mary.add_by_value(50);

    System.out.println();
}

add_by_value

public void add_by_value(int value) {
    add_by_index(i_end + 1, value);
}

測試情境3: remove_by_index

public static void main(String[] args) {
    ArrayImp2 mary = new ArrayImp2(5);

    mary.add_by_value(1);
    mary.add_by_value(2);
    mary.add_by_value(3);
    mary.add_by_value(4);
    mary.add_by_value(5);

    mary.remove_by_index(2);

    System.out.println();
}

remove_by_index

public void remove_by_index(int k) {
    // 驗證範圍
    if (k > i_end || k < 0) return;
    // 清空指定index內容
    array[k] = null;
    // 移除若在中間,需要把後面內容往前遞補
    for (int i = k+1;i <= i_end;i++) {
        array[i-1] = array[i];
        array[i] = null;
    }

    i_end--;
}

測試情境4: remove_by_value

public static void main(String[] args) {
    ArrayImp2 mary = new ArrayImp2(5);

    mary.add_by_value(1);
    mary.add_by_value(2);
    mary.add_by_value(3); // here
    mary.add_by_value(4);
    mary.add_by_value(5);
    
    Integer vv = mary.remove_by_value(3);

    System.out.println();
}

remove_by_value

public void remove_by_value(int value) {
    //輪查
    for (int i = 0;i <= i_end;i++) {
        if (array[i] == value) {
            remove_by_index(i);
            return;
        }
    }
}

測試情境5: search_by_index

public static void main(String[] args) {
    ArrayImp2 mary = new ArrayImp2(5);

    mary.add_by_value(1);
    mary.add_by_value(2);
    mary.add_by_value(3); // here
    mary.add_by_value(4);
    mary.add_by_value(5);
    
    Integer vv = mary.search_by_index(2);

    System.out.println();
}

search_by_index

public Integer search_by_index(int index) {
    // out range
    if (index > i_end || index < 0) return null;
    return array[index];
}

測試情境6: search_by_value

public static void main(String[] args) {
    ArrayImp2 mary = new ArrayImp2(5);

    mary.add_by_value(1);
    mary.add_by_value(2);
    mary.add_by_value(3);
    mary.add_by_value(4); // here, 3
    mary.add_by_value(5);
    
    Integer vv = mary.search_by_value(4);

    System.out.println();
}

remove_by_value

public Integer search_by_value(int value) {
    for (int i = 0; i <= i_end;i++) {
        if (array[i] == value) {
            return i;
        }
    }

    return null;
}

TC:

  1. add_by_index: O(n)
  2. add_by_value: O(1), if expand -> O(n)
  3. remove_by_index: O(n)
  4. remove_by_index: O(n)
  5. search_by_index: O(1)
  6. search_by_value: O(n)