?????作者簡介：大家好，我是黑洞曉威，一名大二學(xué)生，希望和大家一起進步。
??本文收錄于 算法，本專欄是針對大學(xué)生、初學(xué)算法的人準備，解析常見的數(shù)據(jù)結(jié)構(gòu)與算法，同時備戰(zhàn)藍橋杯。

一：數(shù)組理論基礎(chǔ)

首先要知道數(shù)組在內(nèi)存中的存儲方式，這樣才能真正理解數(shù)組相關(guān)的題

數(shù)組是存放在連續(xù)內(nèi)存空間上的相同類型數(shù)據(jù)的集合。

數(shù)組可以方便的通過下標索引的方式獲取到下標下對應(yīng)的數(shù)據(jù)。

舉一個字符數(shù)組的例子，如圖所示：

需要兩點注意的是

• 數(shù)組下標都是從0開始的。
• 數(shù)組內(nèi)存空間的地址是連續(xù)的

正是因為數(shù)組的在內(nèi)存空間的地址是連續(xù)的，所以我們在刪除或者增添元素的時候，就難免要移動其他元素的地址。

例如刪除下標為3的元素，需要對下標為3的元素后面的所有元素都要做移動操作，如圖所示：

二：數(shù)組這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點和缺點是什么？

優(yōu)點：查詢/查找/檢索某個下標上的元素時效率極高。
原因：

第一：每一個元素的內(nèi)存地址在空間存儲上是連續(xù)的。

第二：每一個元素類型相同，所以占用空間大小一樣。

第三：知道第一個元素內(nèi)存地址，知道每一個元素占用空間的大小，又知道下標，所以通過一個數(shù)學(xué)表達式就可以計算出某個下標上元素的內(nèi)存地址。直接通過內(nèi)存地址定位元素，所以數(shù)組的檢索效率是最高的。
注意：

缺點：
第一：由于為了保證數(shù)組中每個元素的內(nèi)存地址連續(xù)，所以在數(shù)組上隨機刪除或者增加元素的時候，效率較低，因為隨機增刪元素會涉及到后面元素統(tǒng)一向前或者向后位移的操作。
第二：數(shù)組不能存儲大數(shù)據(jù)量。
因為很難在內(nèi)存空間上找到一塊特別大的連續(xù)的內(nèi)存空間。
注意：
對于數(shù)組中最后一個元素的增刪，是沒有效率影響的。

三：數(shù)組是如何實現(xiàn)隨機訪問的呢？

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

這個定義里有幾個關(guān)鍵詞，理解了這幾個關(guān)鍵詞，我想你就能徹底掌握數(shù)組的概念了。下面就從我的角度分別給你“點撥”一下。

第一是 線性表（Linear List）。顧名思義，線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向。其實除了數(shù)組，鏈表、隊列、棧等也是線性表結(jié)構(gòu)。

而與它相對立的概念是 非線性表，比如二叉樹、堆、圖等。之所以叫非線性，是因為，在非線性表中，數(shù)據(jù)之間并不是簡單的前后關(guān)系。

第二個是 連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)。正是因為這兩個限制，它才有了一個堪稱“殺手锏”的特性：“隨機訪問”。但有利就有弊，這兩個限制也讓數(shù)組的很多操作變得非常低效，比如要想在數(shù)組中刪除、插入一個數(shù)據(jù)，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作。

說到數(shù)據(jù)的訪問，那你知道數(shù)組是如何實現(xiàn)根據(jù)下標隨機訪問數(shù)組元素的嗎？

我們拿一個長度為10的int類型的數(shù)組int[] a = new int[10]來舉例。在我畫的這個圖中，計算機給數(shù)組a[10]，分配了一塊連續(xù)內(nèi)存空間1000～1039，其中，內(nèi)存塊的首地址為base_address = 1000。

我們知道，計算機會給每個內(nèi)存單元分配一個地址，計算機通過地址來訪問內(nèi)存中的數(shù)據(jù)。當(dāng)計算機需要隨機訪問數(shù)組中的某個元素時，它會首先通過下面的尋址公式，計算出該元素存儲的內(nèi)存地址：

a[i]_address = base_address + i * data_type_size

其中data_type_size表示數(shù)組中每個元素的大小。我們舉的這個例子里，數(shù)組中存儲的是int類型數(shù)據(jù)，所以data_type_size就為4個字節(jié)。這個公式非常簡單，我就不多做解釋了。

這里我要特別糾正一個“錯誤”。問到數(shù)組和鏈表的區(qū)別，很多人都回答說，“鏈表適合插入、刪除，時間復(fù)雜度O(1)；數(shù)組適合查找，查找時間復(fù)雜度為O(1)”。

實際上，這種表述是不準確的。數(shù)組是適合查找操作，但是查找的時間復(fù)雜度并不為O(1)。即便是排好序的數(shù)組，你用二分查找，時間復(fù)雜度也是O(logn)。所以，正確的表述應(yīng)該是，數(shù)組支持隨機訪問，根據(jù)下標隨機訪問的時間復(fù)雜度為O(1)。

四：低效的“插入”和“刪除”原因在哪里？

前面概念部分我們提到，數(shù)組為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，會導(dǎo)致插入、刪除這兩個操作比較低效。現(xiàn)在我們就來詳細說一下，究竟為什么會導(dǎo)致低效？又有哪些改進方法呢？

我們先來看 插入操作。

假設(shè)數(shù)組的長度為n，現(xiàn)在，如果我們需要將一個數(shù)據(jù)插入到數(shù)組中的第k個位置。為了把第k個位置騰出來，給新來的數(shù)據(jù)，我們需要將第k～n這部分的元素都順序地往后挪一位。那插入操作的時間復(fù)雜度是多少呢？你可以自己先試著分析一下。

如果在數(shù)組的末尾插入元素，那就不需要移動數(shù)據(jù)了，這時的時間復(fù)雜度為O(1)。但如果在數(shù)組的開頭插入元素，那所有的數(shù)據(jù)都需要依次往后移動一位，所以最壞時間復(fù)雜度是O(n)。 因為我們在每個位置插入元素的概率是一樣的，所以平均情況時間復(fù)雜度為(1+2+…n)/n=O(n)。

如果數(shù)組中的數(shù)據(jù)是有序的，我們在某個位置插入一個新的元素時，就必須按照剛才的方法搬移k之后的數(shù)據(jù)。但是，如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當(dāng)作一個存儲數(shù)據(jù)的集合。在這種情況下，如果要將某個數(shù)據(jù)插入到第k個位置，為了避免大規(guī)模的數(shù)據(jù)搬移，我們還有一個簡單的辦法就是，直接將第k位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第k個位置。

為了更好地理解，我們舉一個例子。假設(shè)數(shù)組a[10]中存儲了如下5個元素：a，b，c，d，e。

我們現(xiàn)在需要將元素x插入到第3個位置。我們只需要將c放入到a[5]，將a[2]賦值為x即可。最后，數(shù)組中的元素如下： a，b，x，d，e，c。

利用這種處理技巧，在特定場景下，在第k個位置插入一個元素的時間復(fù)雜度就會降為O(1)。這個處理思想在快排中也會用到，我會在排序那一節(jié)具體來講，這里就說到這兒。

我們再來看 刪除操作。

跟插入數(shù)據(jù)類似，如果我們要刪除第k個位置的數(shù)據(jù)，為了內(nèi)存的連續(xù)性，也需要搬移數(shù)據(jù)，不然中間就會出現(xiàn)空洞，內(nèi)存就不連續(xù)了。

和插入類似，如果刪除數(shù)組末尾的數(shù)據(jù)，則最好情況時間復(fù)雜度為O(1)；如果刪除開頭的數(shù)據(jù)，則最壞情況時間復(fù)雜度為O(n)；平均情況時間復(fù)雜度也為O(n)。

實際上，在某些特殊場景下，我們并不一定非得追求數(shù)組中數(shù)據(jù)的連續(xù)性。如果我們將多次刪除操作集中在一起執(zhí)行，刪除的效率是不是會提高很多呢？

我們繼續(xù)來看例子。數(shù)組a[10]中存儲了8個元素：a，b，c，d，e，f，g，h?，F(xiàn)在，我們要依次刪除a，b，c三個元素。

為了避免d，e，f，g，h這幾個數(shù)據(jù)會被搬移三次，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒有更多空間存儲數(shù)據(jù)時，我們再觸發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。

五：實戰(zhàn)解題

1. 移除元素

力扣鏈接

給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。

元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。

示例 1：

輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。你不需要考慮數(shù)組中超出新長度后面的元素。例如，函數(shù)返回的新長度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會被視作正確答案。

暴力解法

這個題目暴力的解法就是兩層for循環(huán)，一個for循環(huán)遍歷數(shù)組元素 ，第二個for循環(huán)更新數(shù)組。

很明顯暴力解法的時間復(fù)雜度是O(n^2)，這道題目暴力解法在leetcode上是可以過的。

代碼如下：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 發(fā)現(xiàn)需要移除的元素，就將數(shù)組集體向前移動一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因為下標i以后的數(shù)值都向前移動了一位，所以i也向前移動一位
                size--; // 此時數(shù)組的大小-1
            }
        }
        return size;

    }
};

• 時間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(1)

雙指針法

思路及算法
由于題目要求刪除數(shù)組中等于val的元素，因此輸出數(shù)組的長度一定小于等于輸入數(shù)組的長度，我們可以把輸出的數(shù)組直接寫在輸入數(shù)組上?？梢允褂秒p指針:右指針right指向當(dāng)前將要處理的元素，左指針left指向下一個將要賦值的位置。

·如果右指針指向的元素不等于val，它一定是輸出數(shù)組的一個元素，我們就將右指針指向的元素復(fù)制到左指針位置，然后將左右指針同時右移;

·如果右指針指向的元素等于val，它不能在輸出數(shù)組里，此時左指針不動，右指針右移一位。

整個過程保持不變的性質(zhì)是:區(qū)間[0, left)中的元素都不等于value。當(dāng)左右指針遍歷完輸入數(shù)組以后，left的值就是輸出數(shù)組的長度。
這樣的算法在最壞情況下(輸入數(shù)組中沒有元素等于value)，左右指針各遍歷了數(shù)組一次。

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指針
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

2.有序數(shù)組的平方

力扣鏈接

給你一個按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序。

示例 1：

輸入：nums = [-4,-1,0,3,10] 輸出：[0,1,9,16,100] 解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]，排序后，數(shù)組變?yōu)?[0,1,9,16,100]

示例 2：

輸入：nums = [-7,-3,2,3,11] 輸出：[4,9,9,49,121]

暴力解法

最直觀的想法，莫過于：每個數(shù)平方之后，排個序，美滋滋，代碼如下：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for (int i = 0; i < A.size(); i++) {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end()); // 快速排序
        return A;
    }
};

這個時間復(fù)雜度是 O(n + nlogn)， 可以說是O(nlogn)的時間復(fù)雜度，但為了和下面雙指針法算法時間復(fù)雜度有鮮明對比，我記為 O(n + nlog n)。

雙指針法

數(shù)組其實是有序的， 只不過負數(shù)平方之后可能成為最大數(shù)了。

那么數(shù)組平方的最大值就在數(shù)組的兩端，不是最左邊就是最右邊，不可能是中間。

此時可以考慮雙指針法了，i指向起始位置，j指向終止位置。

定義一個新數(shù)組result，和A數(shù)組一樣的大小，讓k指向result數(shù)組終止位置。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                // 正數(shù)的相對位置是不變的， 需要調(diào)整的是負數(shù)平方后的相對位置
                result[index--] = nums[left] * nums[left];
                ++left;
            } else {
                result[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return result;
    }
}

最后說一句

感謝大家的閱讀，文章通過網(wǎng)絡(luò)資源與自己的學(xué)習(xí)過程整理出來，希望能幫助到大家。

才疏學(xué)淺，難免會有紕漏，如果你發(fā)現(xiàn)了錯誤的地方，可以提出來，我會對其加以修改。

文章來源地址http://www.zghlxwxcb.cn/news/detail-410974.html

到了這里，關(guān)于最基礎(chǔ)的數(shù)組你真的掌握了嗎？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！