本講內(nèi)容：

數(shù)組定義
數(shù)組特點
應用場景
簡單算法題

數(shù)組定義

定義：數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)。

數(shù)組特點

1. 數(shù)據(jù)有前后關系
線性表
線性：數(shù)據(jù)元素有前后順序，如數(shù)組，鏈表，棧，隊列
非線性：如樹，圖，堆
2. 隨機訪問
數(shù)組支持隨機訪問的原因是因為數(shù)組有連續(xù)的內(nèi)存空間和存儲相同類型的數(shù)據(jù)
3. 插入刪除低效

• 插入
  最好O(1) 最壞O(n) 平均O(n)
  數(shù)組若無序，插入新元素時，可以將第k個位置元素移動到數(shù)組末尾，把新元素插入到第k個位置，此處復雜度為O(1)。
  數(shù)組若有序，插入新元素時，如果新元素小于最大元素，則需要移動前面的數(shù)組元素（此處假設數(shù)組有序遞增）
• 刪除
  最好O(1) 最壞O(n) 平均O(n)
  刪除操作需要搬移元素，保證內(nèi)存的連續(xù)性，因此可以把多次刪除操作合并在一起進行操作，減少搬移次數(shù)，提升性能。

TODO：學習JVM垃圾回收機制對于刪除垃圾元素的做法

4. 數(shù)組的訪問越界問題
訪問數(shù)組的本質(zhì)就是訪問一段連續(xù)內(nèi)存，只要數(shù)組通過偏移計算得到的內(nèi)存地址是可用的，那么程序就可能不會報任何錯誤。
TODO:

為什么大多數(shù)編程語言中，數(shù)組要從 0 開始編號，而不是從 1 開始呢？
從數(shù)組存儲的內(nèi)存模型上來看，“下標”最確切的定義應該是“偏移（offset）”。
如果用 a 來表示數(shù)組的首地址，a[0]就是偏移為 0 的位置，也就是首地址，a[k]就表示偏移 k 個 type_size 的位置，所以計算 a[k]的內(nèi)存地址只需要用這個公式：

a[k]_address = base_address + k * type_size

但是，如果數(shù)組從 1 開始計數(shù)，那我們計算數(shù)組元素 a[k]的內(nèi)存地址就會變?yōu)椋?/p>

a[k]_address = base_address + (k-1)*type_size

對比兩個公式，我們不難發(fā)現(xiàn)，從 1 開始編號，每次隨機訪問數(shù)組元素都多了一次減法運算，對于 CPU 來說，就是多了一次減法指令。
數(shù)組作為非常基礎的數(shù)據(jù)結(jié)構(gòu)，通過下標隨機訪問數(shù)組元素又是其非?；A的編程操作，效率的優(yōu)化就要盡可能做到極致。所以為了減少一次減法操作，數(shù)組選擇了從 0 開始編號，而不是從 1 開始。
除此之外，更重要的是歷史原因，最開始C 語言設計者用 0 開始計數(shù)數(shù)組下標，后來JAVA等語言的設計者也就效仿C語言，從0開始了。

應用場景

業(yè)務場景可以使用容器類數(shù)組
底層的開發(fā)建議都使用數(shù)組

簡單算法題

給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。

示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]

說明:
必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。
盡量減少操作次數(shù)。