岳氏礦泉水

泉源思緒，細品人生

0%

資料結構與演算法筆記 | 陣列 (Array)

發表於 更新於 分類於 ， Disqus：
文章字數： 7.6k 所需閱讀時間 ≈ 38 分鐘

陣列是一種能儲存相同資料型別、固定大小、並使用連續記憶體空間的資料結構。每個元素透過索引 (index) 可以快速存取資料。

舉例而言，陣列可以比喻成一條街，街上的每個住戶都是一個值，其門牌號則是索引。郵局若要送信，只需知道門牌即可正確送達。

不過 Python 的陣列與傳統的陣列有些許不同：

特性 傳統陣列（如 C） Python
資料型別 同類型（int, float） 可混合（int, str）
記憶體配置 連續 背後用動態 array 實作
大小是否固定 是 否，會自動擴充
插入與刪除效率 慢（需位移） 同樣是 $\mathcal{O}(n)$

而所謂連續記憶體，當一塊記憶體是一口氣切下來、一個接一個排好的，就稱為記憶體連續配置 (contiguous memory allocation)。陣列元素的記憶體位置計算方式為：

$$
\text{元素記憶體位址} = \text{陣列記憶體位址} + \text{元素長度} \times \text{元素索引}
$$

Python 因為是高階語言，所以無法輕易查看底層的記憶體配置邏輯，但可以使用 ctypes 模組驗證陣列元素記憶體計算邏輯是否為真：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import ctypes

IntArray = ctypes.c_int * 5
arr = IntArray(1, 3, 5, 7, 9)

base_addr = ctypes.addressof(arr)
elem_size = ctypes.sizeof(ctypes.c_int)

print(f"Base address of arr: {base_addr}")
print(f"Element size: {elem_size} bytes")

# Access elements as ctypes objects, not Python values
for i in range(5):
    expected_addr = base_addr + i * elem_size
    
    # Use the internal _type_ and calculate offset
    element_addr = ctypes.addressof(arr) + i * elem_size
    
    print(f"arr[{i}] = {arr[i]}, address: {element_addr}, expected: {expected_addr}")

# Base address of arr: 4686022064
# Element size: 4 bytes
# arr[0] = 1, address: 4686022064, expected: 4686022064
# arr[1] = 3, address: 4686022068, expected: 4686022068
# arr[2] = 5, address: 4686022072, expected: 4686022072
# arr[3] = 7, address: 4686022076, expected: 4686022076
# arr[4] = 9, address: 4686022080, expected: 4686022080

透過上述執行結果，確實可以發現，陣列元素在底層記憶體配置時，是以該公式進行計算。

宣告方式

1
2
3
4
5
6
7
8
9
k = 5                      # 陣列個數
arr: list[int] = [0] * k   # 宣告陣列

# 賦予元素值
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
1
2
print(arr)
# [1, 2, 3, 4, 5]
1
arr: list[int] = [1, 2, 3, 4, 5]
1
2
print(arr)
# [1, 2, 3, 4, 5]

array 模組

雖然 Python 的陣列可以混合不同型別的資料，但實際上可以使用 array 模組進行操作：

1
2
from array import array
arr = array("i", [1, 2, 3, 4])

結果如下：

1
2
print(arr)
# array('i', [1, 2, 3, 4])

其中 'i' 是 型別碼 (type code)，也就是指定陣列的資料型別，目的是為了達到與傳統陣列相同的功能。

Type code C Type Python Type Minimum size (bytes)
'b' signed char int 1
'B' unsigned char int 1
'u' wchar_t Unicode character 2
'w' Py_UCS4 Unicode character 4
'h' signed short int 2
'H' unsigned short int 2
'i' signed int int 2
'I' unsigned int int 2
'l' signed long int 4
'L' unsigned long int 4
'q' signed long long int 8
'Q' unsigned long long int 8
'f' float float 4
'd' double float 8

陣列的底層原理與效能

特性 靜態陣列 (Static Array) 動態陣列 (Dynamic Array)
記憶體配置 一開始就分配固定大小 根據需求動態擴充記憶體
資料型別 通常需相同（如 C 語言） 依實作而定，Python 允許混合型別
空間效率 高（不需搬移記憶體） 可能有多次搬移與浪費空間
增加元素效率 不允許超出原始容量 可以持續增加（但可能重新配置）
代表語言/結構 C/C++ 陣列、Python array.array Python list、Java ArrayList

動態陣列與 Python list

上面提到 Python 的 list 是個可無限擴充的容器，雖然背後仍使用連續的記憶體空間，但底層邏輯其實是動態陣列：每次 append() 資料時，並不會分配新空間，除非空間不足，才會配置更大一塊記憶體（通常是倍增），將原本的資料放進去，再加入新元素。因此，在 Python 中，list.append(x) 時最壞的效率是 $\mathcal{O}(n)$，平均而言是 $\mathcal{O}(1)$。

空間擴充策略：為什麼倍增？

如果不是倍增，而是每次只多分配一格記憶體給新資料，會發生什麼事？

假設有個陣列，每次 append() 新資料都是建立新陣列，大小為舊的陣列長度 $+1$，接著複製原本所有元素過去，再加上新元素，這樣總成本是：

1
2
3
4
5
加第 1 個元素：複製 0 個
加第 2 個元素：複製 1 個
加第 3 個元素：複製 2 個
...
加第 n 個元素：複製 n-1 個

總複製次數會是：

$$
0 + 1 + 2 + \cdots + (n - 1) = \mathcal{O}(n^{2})
$$

用程式碼實際執行一次，可以建立一個 DynamicArray 類別，然後紀錄複製次數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.data = [None] * self.capacity
        self.copy_count = 0

    def append(self, value):
        if self.size == self.capacity:
            old_data = self.data
            self.capacity += 1
            self.data = [None] * self.capacity
            for i in range(self.size):
                self.data[i] = old_data[i]
                self.copy_count += 1
        self.data[self.size] = value
        self.size += 1

接著初始化陣列，然後加 $1000$ 次：

1
2
3
arr = DynamicArray()
for i in range(1000):
    arr.append(i)

印出結果：

1
2
3
4
5
6
7
print("最終容量：", arr.capacity)
print("實際資料長度：", arr.size)
print("總共複製次數：", arr.copy_count)

# 最終容量： 1000
# 實際資料長度： 1000
# 總共複製次數： 499500

但如果改為倍增，每次的成本會是：

1
2
3
4
5
加第 1 個元素：複製 1 個
加第 2 個元素：複製 2 個
加第 3 個元素：複製 4 個
...
加第 n 個元素：複製 n/2 個

總複製次數會是：

$$
1 + 2 + 4 + \cdots + \dfrac{n}{2} \simeq 2n = \mathcal{O}(n)
$$

將上面的 DynamicArray 類別中容量擴充的邏輯改為 self.capacity *= 2 ，並執行結果後

1
2
3
4
5
6
7
print("最終容量：", arr.capacity)
print("實際資料長度：", arr.size)
print("總共複製次數：", arr.copy_count)

# 最終容量： 1024
# 實際資料長度： 1000
# 總共複製次數： 1023

可以驚人的發現，複製次數竟然比原本的還少！上面的這個現象，其實可以歸結成：若每次僅增加一格，每次新增元素時就必須複製 $n - 1$ 次；改為倍增後，雖然每次都需要擴充兩倍的空間，但是只有在空間不夠的時候才需要搬移。

一維陣列 (1-D Array)

一維陣列是一種線性資料結構，可以視為一串排列成一列的值，每個元素都有對應的索引。

操作 範例程式碼 時間複雜度
查詢 x = arr[i] $\mathcal{O}(1)$
修改 arr[i] = x $\mathcal{O}(1)$
插入 arr.insert(i, x) $\mathcal{O}(n)$
刪除 arr.pop(i) $\mathcal{O}(n)$
走訪陣列 for x in arr: $\mathcal{O}(n)$

查詢、修改與走訪的時間複雜度很好理解，但是為何插入與刪除是 $\mathcal{O}(n)$ 呢？

插入元素

假設一個陣列 arr = [1, 2, 3, 4, 5] ，我們想要在索引 2 與 3 中間插入 8，變成 [1, 2, 3, 8, 4, 5] ，也就是原本 arr[3] 的值變成 8。順序是：

  • 在 arr 尾巴 append(0) ，用於移動資料
  • 將索引值為 3 之後的所有元素都往後移動一格
  • 令 arr[3] = 8

實際操作如下：

1
2
3
4
5
6
7
8
9
10
arr: list[int] = [1, 2, 3, 4, 5]

k = 3                   # 插入索引值
N = 8                   # 插入值

arr.append(0)           # 尾部補 0
for i in range(len(arr) - 1, k, -1):
    arr[i] = arr[i - 1] # 插入位置後向後移動

arr[k] = N              # 取代 arr[k] 為 N

執行結果為：

1
2
print(arr)
# [1, 2, 3, 8, 4, 5]

刪除元素

刪除元素與插入元素相似，只是不需要在尾部補上空格，而是要將最後一個元素刪除。假設我們要刪除索引 2，順序如下：

  • 從目標索引開始，將後面的元素移動到前面
  • 刪除最後一個元素

實際操作如下：

1
2
3
4
5
6
7
8
9
10
arr: list[int] = [1, 2, 3, 4, 5]

k = 2
for i in range(k, len(arr) - 1):
    arr[i] = arr[i + 1] # 插入位置後向後移動

arr.pop(-1)             # 丟掉最後一個元素

print(arr)
# [1, 2, 4, 5]

執行結果為：

1
2
print(arr)
# [1, 2, 4, 5]

練習題

給一個整數陣列 nums，與一個整數 val，請就地 (in-place) 移除所有等於 val 的元素，並返回移除後的陣列長度。不需要維持原本順序，也不需要回傳新的陣列。

1
2
3
輸入: nums = [3, 2, 2, 3], val = 3
輸出: 2
原因: 移除兩個 3，剩下 [2, 2]
解答 
1
2
3
4
5
6
7
8
9
class Solution:
    def removeNum(self, nums: list[int], val: int) -> int:
        write: int = 0
        for read in range(len(nums)):
            if nums[read] != val:
                nums[write] = nums[read]
                write += 1
        
        return write

給定一個整數陣列 nums，請將所有數值為 0 的元素「移動到陣列末端」，但保持非 0 元素的相對順序不變。

注意：

  • 必須「就地 (in-place)」修改陣列
  • 不可以建立新陣列或使用內建 sort/remove 等函式
1
2
輸入: nums = [0, 1, 0, 3, 12]
輸出: [1, 3, 12, 0, 0]
解答 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def moveZeroToEnd(self, nums: list[int]) -> list[int]:
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
    
    for i in range(write, len(nums)):
        nums[i] = 0
    
    return nums

二維陣列 (2-D Array)

二維陣列可以視為陣列的陣列，每個元素本身也是一個陣列，其結構視覺上看起來就是一個表格或矩陣，包含列 (row)與欄 (column)。例如：

1
2
3
4
5
[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
  • 第一層是列（外層 list）
  • 第二層是欄（內層 list）

實務上多以 arr[i][j] 表示第 i 列第 j 欄的元素。

宣告方式

在 Python 中可以使用 list comprehension 建立一個 $m \times n$ 的二維陣列：

1
2
3
rows = 3
cols = 4
matrix: list[list[int]] = [[0] * cols for _ in range(rows)]
1
2
3
4
5
6
print(matrix)
# [
#   [0, 0, 0, 0],
#   [0, 0, 0, 0],
#   [0, 0, 0, 0]
# ]

事實上這個二維陣列在數學上就是一個 $3 \times 4$ 矩陣：

$$
M_{3 \times 4} =
\begin{bmatrix}
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
\end{bmatrix}
$$

但請注意，不能寫成這樣：

1
matrix = [[0] * cols] * rows  # 錯誤：會建立重複參照的列

這樣做會讓所有列指向同一個物件，修改其中一列的元素時，其他列也會改變。除了使用 list comprehension，如果知道二維陣列的長相，也可以直接宣告，例如以下建立一個 $4 \times 4$ 的單位矩陣：

1
2
3
4
I = [[1, 0, 0, 0],
     [0, 1, 0, 0],
     [0, 0, 1, 0],
     [0, 0, 0, 1]]
1
2
3
4
5
print(I)
# [[1, 0, 0, 0],
#  [0, 1, 0, 0],
#  [0, 0, 1, 0],
#  [0, 0, 0, 1]]

數學上的寫法則是：

$$
I_{4} =
\begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
\end{bmatrix}
$$

元素存取與操作

二維陣列的元素存取與修改與一維陣列相似，只是今天多了一個維度需要考慮。

操作 範例程式碼 時間複雜度
查詢 x = arr[i][j] $\mathcal{O}(1)$
修改 arr[i][j] = x $\mathcal{O}(1)$
插入列 arr.insert(i, new_row) $\mathcal{O}(n)$
插入欄 for row in arr: row.insert(j, x) $\mathcal{O}(m)$
刪除列 arr.pop(i) $\mathcal{O}(n)$
刪除欄 for row in arr: row.pop(j) $\mathcal{O}(m)$
走訪全部 for i in range(m): for j in range(n): arr[i][j] $\mathcal{O}(m \times n)$ 
1
2
matrix[0][1] = 10     # 修改第 0 列第 1 欄的值為 10
value = matrix[2][3]  # 取得第 2 列第 3 欄的值

如果想走訪二維陣列，就需要使用巢狀迴圈，但請注意順序：先走訪列，再走訪欄。原因就是宣告陣列時，外層表示的是列，內層則是欄。

1
2
3
for i in range(len(matrix)):         # 列
    for j in range(len(matrix[0])):  # 欄
        matrix[i][j]

更簡潔的寫法是善用 enumerate 函式，同時得到索引與值：

1
2
3
for i, val in enumerate(matrix):
    for j, val in enumerate(row):
        matrix[i][j]

練習題

給一個 $m \times n$ 的整數矩陣 matrix，計算所有元素的總和。

1
2
3
4
5
6
輸入: 
matrix = [
    [1, 2, 3],
    [4, 5, 6]
]
輸出: 21
解答 
1
2
3
4
5
6
7
8
class Solution:
    def sumOfMatrix(self, matrix: list[list[int]]) -> int:
        result = 0
        
        for row in matrix:
            for val in row:
                result +=  val
        return result

給一個 $m \times n$ 的整數矩陣 matrix，計算主對角線（從左上到右下）的總和。

1
2
3
4
5
6
7
8
輸入: 
matrix = [
    [1, 0, 0],
    [0, 5, 0],
    [0, 0, 9]
]

輸出: 15
解答 
1
2
3
4
5
6
7
class Solution:
    def diagonalSum(self, matrix: list[list[int]]) -> int:
        diag_sum = 0

        for i in range(len(matrix)):
            diag_sum += matrix[i][i]
        return diag_sum

給一個 $m \times n$ 的整數矩陣 matrix，就地反轉每一列的元素順序。

1
2
3
4
5
6
7
8
9
10
輸入: 
matrix = [
    [1, 2, 3],
    [4, 5, 6]
]
輸出:
[
    [3, 2, 1],
    [6, 5, 4]
]
解答 
1
2
3
4
5
6
7
class Solution:
    def reverseRowElement(self, matrix: list[list[int]]) -> None:
        for i in range(len(matrix)):
            row = matrix[i]
            n = len(row)
            for j in range(n // 2):
                row[j], row[n - j - 1] = row[n - j - 1], row[j]