學習資源

https://labuladong.online/algo/data-structure-basic/cycle-array/

學習記錄

今天是學習的第 6 天，主要學習了環形陣列技巧及實現：

環形陣列技巧利用求模（餘數）運算，將一個普通陣列變成邏輯上的環形陣列，可以讓我們用 O(1) 的時間在陣列頭部增刪元素，舉個求模的例子：

var arr = [1, 2, 3];
var length = arr.length;

console.log(arr[0 % length]); // 0 % 3 => 0，取 arr[0]
console.log(arr[1 % length]); // 1 % 3 => 1，取 arr[1]
console.log(arr[2 % length]); // 2 % 3 => 2，取 arr[2]
console.log(arr[3 % length]); // 3 % 3 => 0，取 arr[0]，回到開頭！
console.log(arr[4 % length]); // 4 % 3 => 1，取 arr[1]
console.log(arr[5 % length]); // 5 % 3 => 2，取 arr[2]
console.log(arr[6 % length]); // 6 % 3 => 0，取 arr[0]，回到開頭！

環形陣列原理

這段程式碼的關鍵在於求模運算 %，也就是求餘數。

當 i 到達陣列末尾元素時，i + 1 和 arr.length 取餘數又會變成 0，這個時候又會回到陣列頭部，這樣就在邏輯上形成了一個環形陣列。

// 長度為 5 的陣列
var arr = [1, 2, 3, 4, 5];
var i = 0;

// 模擬環形陣列，這個循環永遠不會結束
// 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
while (i < arr.length) {
    console.log(arr[i]);
    i = (i + 1) % arr.length;
}

環形陣列核心原理

環形陣列的關鍵在於維護兩個指針 start 和 end，start 指向第一個有效元素的索引，end 指向最後一個有效元素的下一個索引位置。

索引: 0  1  2  3  4
元素: a  b  _  _  _

start = 0, end = 2

當我們在陣列頭部添加或刪除元素時，只需要移動 start 索引，而在陣列尾部添加或刪除元素時，只需要移動 end 索引。

當 start, end 移動超出了陣列的邊界（< 0 或 >= arr.length）時，我們可以通過求模運算 % 讓它們轉一圈到陣列頭部或尾部繼續工作，這樣就實現了環形陣列的效果。

什麼是左閉右開區間？

左閉右開區間 [start, end) 的含義是：

• 左閉（包含 start）：區間包含 start 這個位置的元素
• 右開（不包含 end）：區間不包含 end 這個位置的元素

假設我們有一個陣列 [a, b, c, d, e]，索引為 [0, 1, 2, 3, 4]

索引: 0  1  2  3  4
元素: a  b  c  d  e

如果我們說區間是 [1, 4)，那麼：

• 包含索引 1：元素 b
• 包含索引 2：元素 c
• 包含索引 3：元素 d
• 不包含索引 4：元素 e 不在區間內

所以 [1, 4) 區間包含的元素是：b, c, d

環形陣列程式碼

class CycleArray {
    constructor(size = 1) {
        this.size = size;
        this.arr = new Array(size);
        // start 指向第一個有效元素的索引，閉區間
        this.start = 0;
        // end 指向最後一個有效元素的下一個索引位置，開區間
        this.end = 0;
        this.count = 0;
    }

    resize(newSize) {
        // 創建新的陣列
        var newArr = new Array(newSize);
        // 將舊的陣列元素複製到新陣列中
        for (var i = 0; i < this.count; i++) {
            newArr[i] = this.arr[(this.start + i) % this.size];
        }
        this.arr = newArr;
        // 重置 start 和 end 指針
        this.start = 0;
        this.end = this.count;
        this.size = newSize;
    }

    // 在陣列頭部添加元素，時間複雜度 O(1)
    addFirst(val) {
        // 當陣列滿時，擴容為原來的兩倍
        if (this.isFull()) {
            this.resize(this.size * 2);
        }
        // 因為 start 是閉區間，所以先左移，在賦值
        this.start = (this.start - 1 + this.size) % this.size;
        this.arr[this.start] = val;
        this.count++;
    }

    // 刪除陣列頭部元素，時間複雜度 O(1)
    removeFirst() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // 因為 start 是閉區間，所以先賦值，再右移
        this.arr[this.start] = null;
        this.start = (this.start + 1) % this.size;
        this.count--;
        // 如果陣列元素數量減少到原大小的四分之一，則減小陣列大小為一半
        if (this.count > 0 && this.count == this.size / 4) {
            this.resize(this.size / 2);
        }
    }

    // 在陣列尾部添加元素，時間複雜度 O(1)
    addLast(val) {
        if (this.isFull()) {
            this.resize(this.size * 2);
        }
        // 因為 end 是開區間，所以是先賦值，再右移
        this.arr[this.end] = val;
        this.end = (this.end + 1) % this.size;
        this.count++;
    }

    // 刪除陣列尾部元素，時間複雜度 O(1)
    removeLast() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // 因為 end 是開區間，所以先左移，再賦值
        this.end = (this.end - 1 + this.size) % this.size;
        this.arr[this.end] = null;
        this.count--;
        // 縮容
        if (this.count > 0 && this.count == this.size / 4) {
            this.resize(this.size / 2);
        }
    }

    // 獲取陣列頭部元素，時間複雜度 O(1)
    getFirst() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        return this.arr[this.start];
    }

    // 獲取陣列尾部元素，時間複雜度 O(1)
    getLast() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // end 是開區間，指向的是下一個元素的位置，所以要減 1
        return this.arr[(this.end - 1 + this.size) % this.size];
    }

    isFull() {
        return this.count === this.size;
    }

    size() {
        return this.count;
    }

    isEmpty() {
        return this.count === 0;
    }
}

// 測試
// {
//   arr: [_, _, _, _, _],
//   count: 0,
//   start: 0,
//   end: 0,
//   size: 5
// }
var arr = new CycleArray(5);

// {
//   arr: [1, _, _, _, _],
//   count: 1,
//   start: 0,
//   end: 1,
//   size: 5
// }
arr.addLast(1);

// {
//   arr: [1, 2, _, _, _],
//   count: 2,
//   start: 0,
//   end: 2,
//   size: 5
// }
arr.addLast(2);

// {
//   arr: [1, 2, _, _, 3],
//   count: 3,
//   start: 4,
//   end: 2,
//   size: 5
// }
arr.addFirst(3);

// {
//   arr: [1, 2, _, 4, 3],
//   count: 4,
//   start: 3,
//   end: 2,
//   size: 5
// }
arr.addFirst(4);

// {
//   arr: [1, 2, _, _, 3],
//   count: 3,
//   start: 4,
//   end: 2,
//   size: 5
// }
add.removeFirst();

學習總結

• 環形陣列技巧利用求模（餘數）運算，將一個普通陣列變成邏輯上的環形陣列
• 環形陣列的關鍵在於維護兩個指針 start 和 end
• 左閉右開區間 [start, end) 的含義是：
  • 左閉（包含 start）：區間包含 start 這個位置的元素
  • 右開（不包含 end）：區間不包含 end 這個位置的元素