通過前面幾個課時的學習，我們了解了線性表、棧、隊列的基本概念，至此，相信你已經掌握了這些數據處理的基本操作，能夠熟練地完成線性表、棧、隊列結構下的增刪查操作。 由于棧和隊列是特殊的線性表，本質上它們都可以被看作是一類基本結構。而數組則可以看成是線性表的一種推廣，它屬于另外一種基本的數據結構。這一課時，我們就來學習數組的概念以及如何用數組實現增刪查的操作。 #### 數組是什么 數組是數據結構中的最基本結構，幾乎所有的程序設計語言都把數組類型設定為固定的基礎變量類型。我們可以把數組理解為一種容器，它可以用來存放若干個相同類型的數據元素。 例如： * 存放的數據是整數型的數組，稱作整型數組； * 存放的數據是字符型的數組，則稱作字符數組； * 另外還有一類數組比較特殊，它是數組的數組，也可以叫作二維數組。 如果用數學的方式來看，我們可以把普通的數組看成是一個向量，那么二維數組就是一個矩陣。不過，二維數組對數據的處理方式并沒有太多特別之處。 數組可以把這些具有相同類型的元素，以一種不規則的順序進行排列，這些排列好的同類數據元素的集合就被稱為數組。 數組在內存中是連續存放的，數組內的數據，可以通過索引值直接取出得到。如下圖所示，我們建立了一個簡單的數組，數組中的每個數據位置都可以放入對應的數據內容。  數據元素 A、B 分別為數組的第一個元素和第二個元素，根據其對應位置分別放入數組空間的第一個和第二個位置。數組的索引值從 0 開始記錄，因此，上圖中數據 A 的索引值是 0，B 的索引值是 1。 實際上數組的索引就是對應數組空間，所以我們在進行新增、刪除、查詢操作的時候，完全可以根據代表數組空間位置的索引值進行。也就是說，只要記錄該數組頭部的第一個數據位置，然后累加空間位置即可。下面我們來具體講一下如何通過數組來實現基于索引的新增、刪除和查找操作。 #### 數組的基本操作 數組在存儲數據時是按順序存儲的，并且存儲數據的內存也是連續的，這就造成了它具有增刪困難、查找容易的特點。同時，棧和隊列是加了限制的線性表，只能在特定的位置進行增刪操作。相比之下，數組并沒有這些限制，可以在任意位置增刪數據，所以數組的增刪操作會更為多樣。下面我們來具體地介紹一下數組的增刪查操作。 * [ ] 數組的新增操作 數組新增數據有兩個情況： * 第一種情況，在數組的最后增加一個新的元素。此時新增一條數據后，對原數據產生沒有任何影響。可以直接通過新增操作，賦值或者插入一條新的數據即可。時間復雜度是 O(1)。 * 第二種情況，如果是在數組中間的某個位置新增數據，那么情況就完全不一樣了。這是因為，新增了數據之后，會對插入元素位置之后的元素產生影響，具體為這些數據的位置需要依次向后挪動 1 個位置。 例如，對于某一個長度為 4 的數組，我們在第 2 個元素之后插入一個元素，那么修改后的數組中就包含了 5 個元素，其中第 1、第 2 個元素不發生變化，第 3 個元素是新來的元素，第 4、第 5 個元素則是原來第 3、第 4 個元素。這一波操作，就需要對一般的數據進行重新搬家。而這個搬家操作，與數組的數據量線性相關，因此時間復雜度是 O(n)。  * [ ] 數組的刪除操作 數組刪除數據也有兩種情況： * 第一種情況，在這個數組的最后，刪除一個數據元素。由于此時刪除一條數據后，對原數據沒有產生任何影響。我們可以直接刪除該數據即可，時間復雜度是 O(1)。 * 第二種情況，在這個數組的中間某個位置，刪除一條數據。同樣的，這兩種情況的區別在于，刪除數據之后，其他數據的位置是否發生改變。由于此時的情況和新增操作高度類似，我們就不再舉例子了。 * [ ] 數組的查找操作 相比于復雜度較高的增刪操作，數組的查找操作就方便一些了。由于索引的存在，數組基于位置的查找操作比較容易實現。我們可以索引值，直接在 O(1) 時間復雜度內查找到某個位置的元素。 例如，查找數組中第三個位置的元素，通過 a[2] 就可以直接取出來。但對于鏈表系的數據結構，是沒有這個優勢的。 不過，另外一種基于數值的查找方法，數組就沒有什么優勢了。例如，查找數值為 9 的元素是否出現過，以及如果出現過，索引值是多少。這樣基于數值屬性的查找操作，也是需要整體遍歷一遍數組的。和鏈表一樣，都需要 O(n) 的時間復雜度。 上面的操作，在很多高級編程語言都已經封裝了響應的函數方法，是不需要自己獨立開發的。例如，新增系列的 push(), unshift(), concat() 和 splice()，刪除系列的 pop(),shift() 和slice()，查找系列的 indexOf() 和 lastIndexOf() 等等。不過別被迷惑，即使是封裝好了的函數，其時間復雜度也不會發生改變。依然是我們上面分析的結果，這些底層原理是需要你理解并掌握的。 #### 數組增刪查操作的特點 通過以上內容的學習，我們發現數組增刪查的操作相比棧、隊列來說，方法更多，操作更為靈活，這都是由它們數據結構的特點決定的。接下來，我們來歸納一下數組增刪查的時間復雜度。 * 增加：若插入數據在最后，則時間復雜度為 O(1)；如果中間某處插入數據，則時間復雜度為 O(n)。 * 刪除：對應位置的刪除，掃描全數組，時間復雜度為 O(n)。 * 查找：如果只需根據索引值進行一次查找，時間復雜度是 O(1)。但是要在數組中查找一個數值滿足指定條件的數據，則時間復雜度是 O(n)。 實際上數組是一種相當簡單的數據結構，其增刪查的時間復雜度相對于鏈表來說整體上是更優的。那么鏈表存在的價值又是什么呢？ * 首先，鏈表的長度是可變的，數組的長度是固定的，在申請數組的長度時就已經在內存中開辟了若干個空間。如果沒有引用 ArrayList 時，數組申請的空間永遠是我們在估計了數據的大小后才執行，所以在后期維護中也相當麻煩。 * 其次，鏈表不會根據有序位置存儲，進行插入數據元素時，可以用指針來充分利用內存空間。數組是有序存儲的，如果想充分利用內存的空間就只能選擇順序存儲，而且需要在不取數據、不刪除數據的情況下才能實現。 #### 數組的案例 例題，假設數組存儲了 5 個評委對 1 個運動員的打分，且每個評委的打分都不相等。現在需要你： 1. 用數組按照連續順序保存，去掉一個最高分和一個最低分后的 3 個打分樣本； 2. 計算這 3 個樣本的平均分并打印。 要求是，不允許再開辟 O(n) 空間復雜度的復雜數據結構。 我們先分析一下題目：第一個問題，要輸出刪除最高分和最低分后的樣本，而且要求是不允許再開辟復雜空間。因此，我們只能在原數組中找到最大值和最小值并刪除。第二個問題，基于刪除后得到的數組，計算平均值。所以解法如下： 1. 數組一次遍歷，過程中記錄下最小值和最大值的索引。對應下面代碼的第 7 行到第 16 行。時間復雜度是 O(n)。 2. 執行兩次基于索引值的刪除操作。除非極端情況，否則時間復雜度仍然是 O(n)。對應于下面代碼的第 18 行到第 30 行。 3. 計算刪除數據后的數組元素的平均值。對應于下面代碼的第 32 行到第 37 行。時間復雜度是 O(n)。 因此，O(n) + O(n) + O(n) 的結果仍然是 O(n)。 代碼如下： ``` public void getScore() { int a[] = { 2, 1, 4, 5, 3 }; max_inx = -1; max_val = -1; min_inx= -1; min_val = 99; for (int i = 0; i < a.length; i++) { if (a[i] > max_val) { max_val = a[i]; max_inx = i; } if (a[i] < min_val) { min_val = a[i]; min_inx = i; } } inx1 = max_inx; inx2 = min_inx; if (max_inx < min_inx){ inx1 = min_inx; inx2 = max_inx; } for (int i = inx1; i < a.length-1; i++) { a[i] = a[i+1]; } for (int i = inx2; i < a.length-1; i++) { a[i] = a[i+1]; } sumscore = 0; for (int i = 0; i < a.length-2; i++) { sumscore += a[i]; } avg = sumscore/3.0; System.out.println(avg); } ``` #### 總結 本節內容主要講解了數組的原理和特性，以及數組的增刪查的操作方法。由于數組中沒有棧和隊列那樣對于線性表的限制，所以增刪查操作變得靈活很多，代碼實現的方法也更多樣，所以我們要根據實際需求選擇適合的方法進行操作。 在實際操作中，我們還要注意根據數組的優缺點合理區分數組和鏈表的使用。數組定義簡單，訪問方便，但在數組中所有元素類型必須相同，數組的最大長度必須在定義時給出，數組使用的內存空間必須連續等。 相對而言，數組更適合在數據數量確定，即較少甚至不需要使用新增數據、刪除數據操作的場景下使用，這樣就有效地規避了數組天然的劣勢。在數據對位置敏感的場景下，比如需要高頻根據索引位置查找數據時，數組就是個很好的選擇了。 #### 練習題 下面，我們給出一道練習題。給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后的數組和新的長度，你不需要考慮數組中超出新長度后面的元素。要求，空間復雜度為 O(1)，即不要使用額外的數組空間。 例如，給定數組 nums = [1,1,2]，函數應該返回新的長度 2，并且原數組 nums 的前兩個元素被修改為 1, 2。 又如，給定 nums = [0,0,1,1,1,2,2,3,3,4]，函數應該返回新的長度 5，并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。這道題我們會在后續的實戰課程中給出答案。