第2章 數組

2.1 數組的基礎知識

數組是一種簡單的數據結構，是由相同類型的元素組成的數據集合，并且占據一塊連續的內存并按照順序存儲數據。面試中出現的數組通常是一維或二維的。最簡單的數組是一維的，其中元素的存取以單一的下標表示。二維數組對應于數學上矩陣的概念，其中元素的存取需要行和列兩個下標。

創建數組時需要先指定數組的容量大小，然后根據容量大小分配內存。即使只在數組中存儲一個數字，也需要為所有的數據預先分配內存。因此，數組的空間效率不一定很高，可能會有空閑的區域沒有得到充分利用。

為了解決數組空間效率不高的問題，人們又設計實現了動態數組，如Java中的ArrayList。動態數組既保留了數組時間效率高的特性，又能夠在數組中不斷添加新的元素。為了避免浪費，可以先為數組分配較小的內存空間，然后在需要的時候在數組中添加新的數據。當數據的數目增加導致數組的容量不足時，需要重新分配一塊更大的空間（通常新的容量是之前容量的2倍），把之前的數據復制到新的數組中，再把之前的內存釋放。這樣能減少內存的浪費，但每次擴充數組容量時都有大量的額外操作，這對時間性能有負面影響。