什么是數(shù)組？
大家好呀，我是蛋蛋。瞎起題目的嘴強王者，亂寫界的無冕之王。
提到數(shù)組，想必臭寶們都不陌生。說不定已經昂起腦瓜抖著腿，小眼神兒斜著來一句：“就那個隨隨便便用腳趾甲就能學會的數(shù)組？”
數(shù)組，你確定很簡單？
自信點，語氣肯定點，數(shù)組確實很簡單。
但是我還要講。
當然開始之前，你要確定你先看過下面這篇：
。。。
數(shù)組，一種基礎的的線性數(shù)據(jù)結構。不管寫什么代碼基本上都會用到數(shù)組，它也是面試中面試官喜歡提問的高頻問題。
鑒于它勞模的身份，對數(shù)組的考察基本都是考察代碼方面的問題。
但是萬變不離其宗，解決數(shù)組方面問題的萬能鑰匙，其實就是深刻的認識數(shù)組本身的深淺
什么是數(shù)組？
首先什么是數(shù)組？
數(shù)組是一種基礎的線性數(shù)據(jù)結構，它是用連續(xù)的一段內存空間，來存儲相同數(shù)據(jù)類型數(shù)據(jù)的集合。
這里面有兩個重點：
線性數(shù)據(jù)結構
連續(xù)內存存儲相同數(shù)據(jù)類型
線性數(shù)據(jù)結構
線性數(shù)據(jù)結構，顧名思義，像線一樣的數(shù)據(jù)結構，又硬又直的典型代表。
線性數(shù)據(jù)結構是有限的，它是某類元素的集合并且記錄著元素之間的一組順序關系，除了首尾之外，其余元素之間有且只有一個前驅和后繼。
除了數(shù)組以外，像單鏈表、棧、隊列等也是典型的線性數(shù)據(jù)結構。
連續(xù)內存存儲的相同數(shù)據(jù)類型
以一個長度為 6 的 int 類型的數(shù)組為例，理解一下“連續(xù)內存存儲相同數(shù)據(jù)類型”數(shù)組的樣砸。
上圖中的計算機給數(shù)組 a 分配了一塊連續(xù)的內存空間 1000 - 1005，首地址 address[0] = 1000。
因為連續(xù)，且對于數(shù)組來說下標從 0 開始的，所有對于數(shù)組中的每個元素來說，它的內存地址就很好計算：
address[i] = address[0] + i
數(shù)組的操作
從上面可以看出，連續(xù)內存存儲使得數(shù)組有一個天然的優(yōu)勢，這個優(yōu)勢就是可以根據(jù)下標，快速的隨意訪問任意一個位置的數(shù)組元素。
因為數(shù)組可以保證不管你訪問哪個元素，只要給出下標，只需進行一次操作，就可以定位到元素的位置，從而拿出這個位置上的值。
這步操作的時間復雜度就是 O(1)。
當然 God 是公平的，在查找上讓數(shù)組當了快男，那必定讓它在插入和刪除上加上“持久”技能點。
在這你要明白，持久意味著花的時間多（低效）。這么看來，在數(shù)據(jù)結構與算法中，秒男成了褒義詞。
這種插入和刪除的“持久”，是如何產生的呢？
這還是要從“連續(xù)內存存儲”上找原因，真所謂快也它，慢也它。
連續(xù)的內存使得在插入或者刪除的元素的時候，其它元素也要相應的移動。
比如我們在下標為 2 的位置上插入一個元素 29：
為了保持連續(xù)內存存儲，在下標為 2 的位置上插入 29，原先 2 - 5 下標位置上元素都要向后一步走，可以看出這一步操作的時間復雜度為 O(n)。
當然在這我必須要強調一點的是，插入的時間復雜度其實根據(jù)情況的不同而不同，在這里主要因為 懶 手疼，沒有都列出來，畢竟我的臭寶們是最聰明噠。
一般我都是按照最壞情況時間復雜度來算。對于插入來說，最好的情況肯定是插在末尾，這樣所有的元素都不用動，時間復雜度為 O(1)，那最壞的情況就是在數(shù)組的開頭插入，這樣所有的元素都要動，時間復雜度就成了 O(n)，請大家一定要注意。
對刪除來說，和插入操作也差不多，比如我們刪除下標為 2 位置上的元素。
刪除了下標 2 位置上的數(shù)字 a[2]， 原來下標 3 - 5 位置上的元素統(tǒng)統(tǒng)向前一步走。
同樣對于刪除來說，最好情況是刪除末尾的元素，時間復雜度為 O(1)，最壞的情況是刪除首位的元素，時間復雜度是 O(n)。
數(shù)組的查找、插入和刪除這 3 個操作講完以后，還有最后一點提醒一下大家，在做數(shù)組類問題的時候要注意數(shù)組越界的問題。
數(shù)組越界，簡單來說就是對于一個大小為 n 的數(shù)組，它的下標應是 0 到 n-1，對這 n 個位置的元素之外的訪問，就是非法的，這就叫做“越界”。
比如對于下面這兩行代碼：
lst = [1,2,3,4]print(lst[4])
編譯一下，就會提示 IndexError : list index out of range。
臭寶們平時寫數(shù)組的時候一定要注意，不然一不小心就 out 了。
到這里，簡單的數(shù)組就講完啦，能忍著看到這的都是真愛呀。碼字碼的手都痛啦，點贊在看留言么么噠給我刷起來～
我是蛋蛋，咱們下次見～
