# [資演] 3-Array & Python list
###### tags: `資演`

Array (陣列) 是一種最常用的資料結構，也是最簡單的資料結構。一個array是一種相同種類的物件的簡單集合。我們可以看到無數array的應用，包括但不僅限於在電腦科學中。

## Array 是什麼？


我們可以把array想做是一盒裝滿滿的馬卡龍：
* 盒子只能裝馬卡龍（不能裝蛋糕、麻糬）
* 所有在盒子裡的馬卡龍都是相鄰的（沒有空位）
* 每個馬卡龍都可以用它的位置唯一地指定
* 盒子的大小不能改變

這對應到的array的性質分別是：
* 一個array只能儲存單一型別的資料
* 在電腦的記憶體裡面，array占有的是連續的一串記憶體
* 每個array中的element(元素)都對應到一個index(索引)
* 一個array的長度必須事先指定

:::info
在電腦科學中，array是一種用來儲存**同一種資料**的資料結構。在一個array裡面，每個element都可以用一個index唯一地指定。在電腦裡面，array占有的記憶體是連續並且相鄰的，這樣就可以藉由index的計算來知道下一個element是什麼。
:::

## Array 的種類
* 單維 array
一個element可以用**一個單一的index**指定。
可以想成是一盒馬卡龍，我們只要知道那個馬卡龍在那個盒子裡面是排在第幾個，就能夠找到它。例如，第2個馬卡龍，我們就用`a[2]`表示。
* 多維 array
一個element必須用**一組index**指定。
想像現在有一個大箱子，裡面裝著很多很多盒馬卡龍。要找到一個特定的馬卡龍，我們除了必須知道它在盒子裡面的位子以外，還必須知道它在第幾盒，例如，第5盒的第2個馬卡龍，我們可以用`a[5][2]`來表示。這是一個2維array的例子。
我們當然可以繼續延伸。現在我們有一個貨櫃，裡面有很多很多箱馬卡龍，要找到一個特定的馬卡龍，除了前面提到的盒子和盒內位置外，還必須知道是在哪一個箱子裡面。例如，第10箱的第5盒中的第2個馬卡龍，表示為`a[10][5][2]`。這就是一個3維array。我們可以一直推廣下去，每次都用一個更大的容器把很多個相同的小容器放進去，當我們要特定其中一個element的時候，就把它在每一種容器的位置講清楚。我們也可以指定某一盒特定的馬卡龍（而不是某一顆馬卡龍），或著是某一箱馬卡龍在貨櫃中的位置。例如，在貨櫃中的第10箱馬卡龍，我們可以寫成`a[10]`；在貨櫃中的第10箱的第5盒，我們就寫成`a[10][5]`。

## 電腦怎麼儲存array？
我們前面講到，array占有的記憶體是連續並且相鄰的。
這就像是我們知道每個馬卡龍的厚度是3公分，一個盒子可以裝10個馬卡龍，那麼這個盒子的長度就是30公分，其中第0個馬卡龍（沒錯，從0開始）占有的是0公分到3公分的位置，第1個馬卡龍是3公分到6公分...以此類推。所以我們如果知道馬卡龍的位置是在盒子從頭算起的的第6公分到第9公分，則我們可以回推，這顆馬卡龍的編號是2；反過來說，如果我們知道一顆馬卡龍的編號是3，那我們就能夠算出它在盒子中佔據的位置應該是第9公分至第12公分。

那麼，array是怎樣的情形呢？現在想像一個由整數組成的array。每個整數占有的記憶體是4個單位。另外，我們那個整數**在記憶體中占有的位置的起點**當作是那個整數的地址（位址, address），也就是說，第3顆馬卡龍佔據的位置是第9公分至第12公分，則他的位址就是在9公分處。一個array的位址相當於它的第0個element的起點位址。

至於多維array，我們就把它們**壓平**來儲存。這是什麼意思呢？以2維的array為例，我們可以把2維的array看成一個array的array，也就是一堆array的有序集合。所以在儲存這個2維array的時候，我們可以按照順序儲存這些array：

同樣地，對於3維array，我們可以看成是一堆2維array的有序集合。也就是說，我們只要遞迴地按照順序儲存那些2維array就可以了，這邊便不再贅述。

## Python 裡的 array
在Python裡面，我們可以使用array模組或是numpy模組裡面的array來進行array的操作。以下以numpy的array為例。

import numpy as np

# 創建一個1維array
a = np.array([1, 2, 3, 4, 5])

# 巡訪1維array a
for elem in a:
    print(elem)

# 創建一個2維array
b = np.array([[11, 15, 10, 6], 
            [10, 14, 11, 5],
            [12, 17, 12, 8],
            [15, 18, 14, 9]])

# 巡訪2維array b
for row in b:
    for elem in row:
        print(elem)

## 什麼是 Python list？
一個list是用來儲存一些東西的有序集合。注意在這邊我們並沒有強調需要單一型別，因為list可以儲存各種型別的東西。

## Python list 的操作

# 創建一個list
my_list = [5, 2, 3, 1, 4]

# 獲取 list 的 element
print(my_list[2])

# 巡訪 my_list: 方法1
for i in range(len(my_list)):
    print(3 * my_list[i])

# 巡訪 my_list: 方法2
for elem in my_list:
    print(3 * elem)

# 在第4個位置插入元素15
my_list.insert(4,15)

# 在尾端位置新增元素55
my_list.append(55)

# 讓這個list變成一個按照順序排好的list
my_list.sort()

:::spoiler 我們現在如果想要加總這個list的所有元素呢？

def sum(a):
    sum = 0
    for elem in my_list:
        sum += elem
    return sum

:::

## 例題
* 尋找遺失的數字
給定一個不一定有排序好的 $n-1$ 個整數，已知這些整數中包含由 $1$ 到 $n$ 其中少了一個數字的所有整數，請找出那個少掉的整數。
Example:

    Input: a = [1, 2, 4, 6, 3, 7, 8]
    Output: 5

    Input: a = [1, 2, 3, 5]
    Output: 4

:::spoiler 解答
在這邊我們應用到一個性質：從 $1$ 到 $n$ 的所有整數總和是 $n(1+n)/2$。我們把這個總和減去list所有element的總和，答案就是少掉的那個數。這邊我們利用到我們剛剛寫出來的sum函式：

    def getMissingNo(a):
        n = len(a) + 1
        total = n * (n + 1)/2
        sum_of_a = sum(a)
        return total - sum_of_a

:::

* 轉置(transpose)一個2維的list
給定一個2維的list，找出他的轉置list。

    Input: a = [[1, 2], 
                [3, 4]]
    Output: [[1, 3],
            [2, 4]]
    
    Input: a = [[1, 2, 3], 
                [4, 5, 6]]
    Output: [[1, 4],
            [2, 5], 
            [3, 6]]

:::spoiler 解答
首先，我們必須知道這個2維list的大小，也就是這個2維list底下有幾個1維list，每個1維list裡面又有幾個element。

    def transpose(a):
        # 這個2維list底下有幾個1維list
        m = len(a)
        
        # 每個1維list裡面有幾個element
        n = len(a[0])
        
        # 初始化一個2維list
        # 底下有n個1維list，每個1維list有m個element
        b = [[0] * m]*n
        
        # 把 element 塞進去
        for i in range(n):
            for j in range(m):
                b[i][j] = a[j][i]
                
        return b

當然，如果使用numpy，你可以更簡單地進行同樣的工作：

    import numpy as np
    
    def transpose(a):
        matrix = np.array(a)
        b = list(matrix.T)
        
        return b

:::