上一課時主要講解了一些常用的數據結構和它們的使用技巧，以及一些經典的例題。 然而，僅僅掌握好它們不足以應付大廠的算法面試的。為了達到對時間和空間復雜度的理想要求，本節課探究高級數據結構，它們的實現要比那些常用的數據結構要復雜得多。其中重點介紹： * 優先隊列 * 圖 * 前綴樹 * 線段樹 * 樹狀數組 掌握好高級數據結構的性質以及所適用的場合，在分析問題的時候回歸本質，很多題目都能迎刃而解。 * [ ] 優先隊列（Priority Queue） * 特點 能保證每次取出的元素都是隊列中優先級別最高的。優先級別可以是自定義的，例如，數據的數值越大，優先級越高；或者數據的數值越小，優先級越高。優先級別甚至可以通過各種復雜的計算得到。 * 應用場景 從一堆雜亂無章的數據當中按照一定的順序（或者優先級）逐步地篩選出部分乃至全部的數據。 舉例：任意一個數組，找出前?k?大的數。 解法 1：先對這個數組進行排序，然后依次輸出前?k?大的數，復雜度將會是?O(nlogn)，其中，n?是數組的元素個數。這是一種直接的辦法。 解法 2：使用優先隊列，復雜度優化成?O(k + nlogk)。 當數據量很大（即?n?很大），而?k?相對較小的時候，顯然，利用優先隊列能有效地降低算法復雜度。因為要找出前?k?大的數，并不需要對所有的數進行排序。 * [ ] 實現 優先隊列的本質是一個二叉堆結構。堆在英文里叫?Binary Heap，它是利用一個數組結構來實現的完全二叉樹。換句話說，優先隊列的本質是一個數組，數組里的每個元素既有可能是其他元素的父節點，也有可能是其他元素的子節點，而且，每個父節點只能有兩個子節點，很像一棵二叉樹的結構。 ? 牢記下面優先隊列有三個重要的性質。 1. 數組里的第一個元素?array[0]?擁有最高的優先級別。 2. 給定一個下標 i，那么對于元素 array[i] 而言： * 它的父節點所對應的元素下標是 (i-1)/2 * 它的左孩子所對應的元素下標是 2×i + 1 * 它的右孩子所對應的元素下標是 2×i + 2 3. 數組里每個元素的優先級別都要高于它兩個孩子的優先級別。 優先隊列最基本的操作有兩個。 * 1. 向上篩選（sift?up / bubble up） * 當有新的數據加入到優先隊列中，新的數據首先被放置在二叉堆的底部。 * 不斷進行向上篩選的操作，即如果發現該數據的優先級別比父節點的優先級別還要高，那么就和父節點的元素相互交換，再接著往上進行比較，直到無法再繼續交換為止。 時間復雜度：由于二叉堆是一棵完全二叉樹，并假設堆的大小為?k，因此整個過程其實就是沿著樹的高度往上爬，所以只需要?O(logk)?的時間。 * 2. 向下篩選（sift down / bubble down） * 當堆頂的元素被取出時，要更新堆頂的元素來作為下一次按照優先級順序被取出的對象，需要將堆底部的元素放置到堆頂，然后不斷地對它執行向下篩選的操作。 * 將該元素和它的兩個孩子節點對比優先級，如果優先級最高的是其中一個孩子，就將該元素和那個孩子進行交換，然后反復進行下去，直到無法繼續交換為止。 ? 時間復雜度：整個過程就是沿著樹的高度往下爬，所以時間復雜度也是?O(logk)。 因此，無論是添加新的數據還是取出堆頂的元素，都需要?O(logk)?的時間。 * [ ] 初始化 優先隊列的初始化是一個最重要的時間復雜度，是分析運用優先隊列性能時必不可少的，也是經常容易弄錯的地方。 舉例：有?n?個數據，需要創建一個大小為?n?的堆。 誤區：每當把一個數據加入到堆里，都要對其執行向上篩選的操作，這樣一來就是?O(nlogn)。 解法：在創建這個堆的過程中，二叉樹的大小是從?1?逐漸增長到?n?的，所以整個算法的復雜度經過推導，最終的結果是 O(n)。 注意：算法面試中是不要求推導的，你只需要記住，初始化一個大小為?n?的堆，所需要的時間是?O(n)?即可。 * [ ] 例題分析 LeetCode 第?347?題：給定一個非空的整數數組，返回其中出現頻率前?k?高的元素。 說明： * 你可以假設給定的?k?總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。 * 你的算法的時間復雜度必須優于?O(nlogn) ，n?是數組的大小 示例：car，car，book，desk，desk，desk * [ ] 解題思路 這道題的輸入是一個字符串數組，數組里的元素可能會重復一次甚至多次，要求按順序輸出前?k?個出現次數最多的字符串。 解這類求"前 k 個"的題目，關鍵是看如何定義優先級以及優先隊列中元素的數據結構。 * 題目中有”前?k?個“這樣的字眼，應該很自然地聯想到優先隊列。 * 優先級別可以由字符串出現的次數來決定，出現的次數越多，優先級別越高，反之越低。 * 統計詞頻的最佳數據結構就是哈希表（Hash?Map），利用一個哈希表，就能快速地知道每個單詞出現的次數。 * 將單詞和其出現的次數作為一個新的對象來構建一個優先隊列，那么這個問題就很輕而易舉地解決了。 建議：這道題是利用優先隊列處理問題的典型，建議好好練習。 ``` Desk (3) ?/ ? ?\ ?car(2) ? book(1)?? ? ? ??? ``` ? * [ ] 圖（Graph） * 基本知識點 圖可以說是所有數據結構里面知識點最豐富的一個，最基本的知識點如下。 * 階（Order）、度：出度（Out-Degree）、入度（In-Degree） * 樹（Tree）、森林（Forest）、環（Loop） * 有向圖（Directed Graph）、無向圖（Undirected Graph）、完全有向圖、完全無向圖 * 連通圖（Connected Graph）、連通分量（Connected Component） * 存儲和表達方式：鄰接矩陣（Adjacency Matrix）、鄰接鏈表（Adjacency List） 圍繞圖的算法也是五花八門。 * 圖的遍歷：深度優先、廣度優先 * 環的檢測：有向圖、無向圖 * 拓撲排序 * 最短路徑算法：Dijkstra、Bellman-Ford、Floyd Warshall * 連通性相關算法：Kosaraju、Tarjan、求解孤島的數量、判斷是否為樹 * 圖的著色、旅行商問題等 以上的知識點只是圖論里的冰山一角，對于算法面試而言，完全不需要對每個知識點都一一掌握，而應該有的放矢地進行準備。 * [ ] 必會知識點 根據長期的經驗總結，以下的知識點是必須充分掌握并反復練習的。 * 圖的存儲和表達方式：鄰接矩陣（Adjacency Matrix）、鄰接鏈表（Adjacency List） * 圖的遍歷：深度優先、廣度優先 * 二部圖的檢測（Bipartite）、樹的檢測、環的檢測：有向圖、無向圖 * 拓撲排序 * 聯合-查找算法（Union-Find） * 最短路徑：Dijkstra、Bellman-Ford 其中，環的檢測、二部圖的檢測、樹的檢測以及拓撲排序都是基于圖的遍歷，尤其是深度優先方式的遍歷。而遍歷可以在鄰接矩陣或者鄰接鏈表上進行，所以掌握好圖的遍歷是重中之重！因為它是所有其他圖論算法的基礎。 至于最短路徑算法，能區分它們的不同特點，知道在什么情況下用哪種算法就很好了。對于有充足時間準備的面試者，能熟練掌握它們的寫法當然是最好的。 建議：LeetCode 里邊有許多關于圖論的算法題，而且都是非常經典的題目，可以通過練習解題來熟練掌握必備知識。 * [ ] 例題分析 LeetCode 第?785?題：給定一個無向圖 graph，當這個圖為二部圖時返回 true。 提示：如果能將一個圖的節點集合分割成兩個獨立的子集 A 和 B，并使圖中的每一條邊的兩個節點一個來自 A 集合，一個來自 B 集合，就將這個圖稱為二部圖。 * [ ] 解題思路 判斷一個給定的任意圖是否為二部圖，就必須要對該圖進行一次遍歷： * 深度優先 * 廣度優先 （關于深度優先和廣度優先算法，將在第?06?節課進行詳細討論）。 二部圖，圖的所有頂點可以分成兩個子集 U 和 V，子集里的頂點互不直接相連，圖里面所有的邊，一頭連著子集 U 里的頂點，一頭連著子集 V 里的頂點。 1. 給圖里的頂點涂上顏色，子集?U?里的頂點都涂上紅色，子集?V?里的頂點都涂上藍色。 2. 開始遍歷這個圖的所有頂點，想象一下手里握有紅色和藍色的畫筆，每次交替地給遍歷當中遇到的頂點涂上顏色。 3. 如果這個頂點還沒有顏色，那就給它涂上顏色，然后換成另外一支畫筆。 4. 下一個頂點，如果發現這個頂點已經涂上了顏色，而且顏色跟我手里畫筆的顏色不同，那么表示這個頂點它既能在子集?U?里，也能在子集?V?里。 5. 所以，它不是一個二部圖。 * [ ] 前綴樹（Trie） * 應用場景 前綴樹被廣泛地運用在字典查找當中，也被稱為字典樹。 舉例：給定一系列字符串，這些字符串構成了一種字典，要求你在這個字典當中找出所有以“ABC”開頭的字符串。 * 解法 1：暴力搜索 直接遍歷一遍字典，然后逐個判斷每個字符串是否由“ABC”開頭。假設字典很大，有?N?個單詞，要對比的不是“ABC”，而是任意的，那不妨假設所要對比的開頭平均長度為?M，那么時間復雜度是?O(M×N)。 * 解法 2：前綴樹 如果用前綴樹頭幫助對字典的存儲進行優化，那么可以把搜索的時間復雜度下降為?O(M)，其中?M?表示字典里最長的那個單詞的字符個數，在很多情況下，字典里的單詞個數?N?是遠遠大于?M?的。因此，前綴樹在這種場合中是非常高效的。 * [ ] 經典應用 1. 網站上的搜索框會羅列出以搜索文字作為開頭的相關搜索信息，這里運用了前綴樹進行后端的快速檢索。 2. 漢字拼音輸入法的聯想輸出功能也運用了前綴樹。 舉例：假如有一個字典，字典里面有如下詞："A"，"to"，"tea"，"ted"，"ten"，"i"，"in"，"inn"，每個單詞還能有自己的一些權重值，那么用前綴樹來構建這個字典將會是如下的樣子： 性質 1. 每個節點至少包含兩個基本屬性。 * children：數組或者集合，羅列出每個分支當中包含的所有字符 * isEnd：布爾值，表示該節點是否為某字符串的結尾 2. 前綴樹的根節點是空的 所謂空，即只利用到這個節點的?children?屬性，即只關心在這個字典里，有哪些打頭的字符。 3. 除了根節點，其他所有節點都有可能是單詞的結尾，葉子節點一定都是單詞的結尾。 實現 前綴樹最基本的操作就是兩個：創建和搜索。 1. 創建 * 遍歷一遍輸入的字符串，對每個字符串的字符進行遍歷 * 從前綴樹的根節點開始，將每個字符加入到節點的?children?字符集當中。 * 如果字符集已經包含了這個字符，則跳過。 * 如果當前字符是字符串的最后一個，則把當前節點的?isEnd?標記為真。 由上，創建的方法很直觀。 前綴樹真正強大的地方在于，每個節點還能用來保存額外的信息，比如可以用來記錄擁有相同前綴的所有字符串。因此，當用戶輸入某個前綴時，就能在?O(1)?的時間內給出對應的推薦字符串。 2. 搜索 與創建方法類似，從前綴樹的根節點出發，逐個匹配輸入的前綴字符，如果遇到了就繼續往下一層搜索，如果沒遇到，就立即返回。 * [ ] 例題分析 LeetCode 第?212?題：給定一個二維網格?board?和一個字典中的單詞列表 words，找出所有同時在二維網格和字典中出現的單詞。 單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母在一個單詞中不允許被重復使用。 說明：你可以假設所有輸入都由小寫字母?a-z?組成。 * [ ] 解題思路 這是一道出現較為頻繁的難題，題目給出了一個二維的字符矩陣，然后還給出了一個字典，現在要求在這個字符矩陣中找到出現在字典里的單詞。 由于字符矩陣的每個點都能作為一個字符串的開頭，所以必須得嘗試從矩陣中的所有字符出發，上下左右一步步地走，然后去和字典進行匹配，如果發現那些經過的字符能組成字典里的單詞，就把它記錄下來。 可以借用深度優先的算法來實現（關于深度優先算法，將在第 06 節課深入探討），如果你對它不熟悉，可以把它想象成走迷宮。 字典匹配的解法 1：每次都循環遍歷字典，看看是否存在字典里面，如果把輸入的字典變為哈希集合的話，似乎只需要?O(1)?的時間就能完成匹配。 但是，這樣并不能進行前綴的對比，即，必須每次都要進行一次全面的深度優先搜索，或者搜索的長度為字典里最長的字符串長度，這樣還是不夠高效。 字典匹配的解法 2：對比字符串的前綴，借助前綴樹來重新構建字典。 假如在矩陣里遇到了一個字符”V”，而字典里根本就沒有以“V”開頭的字符串，則不需要將深度優先搜索進行下去，可以大大地提高搜索效率。 構建好了前綴樹之后，每次從矩陣里的某個字符出發進行搜索的時候，同步地對前綴樹進行對比，如果發現字符一直能被找到，就繼續進行下去，一步一步地匹配，直到在前綴樹里發現一個完整的字符串，把它輸出即可。 * [ ] 線段樹（Segment Tree） 舉例：假設有一個數組?array[0 … n-1]， 里面有?n?個元素，現在要經常對這個數組做兩件事。 1. 更新數組元素的數值 2. 求數組任意一段區間里元素的總和（或者平均值） 解法 1：遍歷一遍數組。 * 時間復雜度?O(n)。 解法 2：線段樹。 * 線段樹，就是一種按照二叉樹的形式存儲數據的結構，每個節點保存的都是數組里某一段的總和。 * 適用于數據很多，而且需要頻繁更新并求和的操作。 * 時間復雜度 O(logn)。 **實現** 舉例：數組是?[1, 3, 5, 7, 9,?11]，那么它的線段樹如下。 根節點保存的是從下標?0?到下標?5?的所有元素的總和，即?36。左右兩個子節點分別保存左右兩半元素的總和。按照這樣的邏輯不斷地切分下去，最終的葉子節點保存的就是每個元素的數值。 解法： 1. 更新數組里某個元素的數值 從線段樹的根節點出發，更新節點的數值，它保存的是數組元素的總和。修改的元素有可能會落在線段樹里一些區間里，至少葉子節點是肯定需要更新的，所以，要做的是從根節點往下，判斷元素的下標是否在左邊還是右邊，然后更新分支里的節點大小。因此，復雜度就是遍歷樹的高度，即?O(logn)。 2. 對數組某個區間段里的元素進行求和 方法和更新操作類似，首先從根節點出發，判斷所求的區間是否落在節點所代表的區間中。如果所要求的區間完全包含了節點所代表的區間，那么就得加上該節點的數值，意味著該節點所記錄的區間總和只是所要求解總和的一部分。接下來，不斷地往下尋找其他的子區間，最終得出所要求的總和。 建議：線段樹的實現書寫起來有些繁瑣，需要不斷地練習。 * [ ] 例題分析 LeetCode 第?315?題：給定一個整數數組 nums，按要求返回一個新數組 counts，使得數組 counts 有該性質——counts[i] 的值是 nums[i] 右側小于?nums[i] 的元素的數量。 ? 示例 ``` 輸入：[5, 2, 6, 1] 輸出：[2, 1, 1, 0]? ``` 解釋 * 5 的右側有 2 個更小的元素（2 和 1） * 2 的右側僅有 1 個更小的元素（1） * 6 的右側有 1 個更小的元素（1） * 1 的右側有 0 個更小的元素 **解題思路** 給定一個數組?nums，里面都是一些整數，現在要求打印輸出一個新的數組?counts，counts?數組的每個元素?counts[i]?表示?nums?中第?i?個元素右邊有多少個數小于?nums[i]。 例如，輸入數組是?[5, 2,?6, 1]，應該輸出的結果是?[2, 1, 1, 0]。 因為，對于?5，右邊有兩個數比它小，分別是?2?和?1，所以輸出的結果中，第一個元素是?2；對于?2，右邊只有?1?比它小，所以第二個元素是?1，類推。 如果使用線段樹解法，需要理清線段樹的每個節點應該需要包含什么樣的信息。 線段樹每個節點記錄的區間是數組下標所形成的區間，然而對于這道題，因為要統計的是比某個數還要小的數的總和，如果把分段的區間設計成按照數值的大小來劃分，并記錄下在這個區間中的數的總和，就能快速地知道比當前數還要小的數有多少個。 1. 首先，讓從線段樹的根節點開始，根節點記錄的是數組里最小值到最大值之間的所有元素的總和，然后分割根節點成左區間和右區間，不斷地分割下去。 2. 初始化，每個節點記錄的在此區間內的元素數量是?0，接下來從數組的最后一位開始往前遍歷，每次遍歷，判斷這個數落在哪個區間，那么那個區間的數量加一。 3. 遇到?1，把它加入到線段樹里，此時線段樹里各個節點所統計的數量會發生變化。 4. 當前所遇到的最小值就是?1。 5. 把?6?加入到線段樹里。 6. 求比?6?小的數有多少個，即查詢線段樹，從?1?到?5?之間有多少個數。 7. 從根節點開始查詢。由于所要查詢的區間是?1?到?5，無法包含根節點的區間?1?到?6，所以繼續往下查詢。 8. 左邊，區間?1?到?3?被完全包含在?1?到?5?之間，把該節點所統計好的數返回。 9. 右邊，區間?1?到?5?跟區間?4?到?6?有交叉，繼續往下看，區間?4?到?5?完全被包含在?1?到?5?之間，所以可以馬上返回，并把統計的數量相加。 10. 最后得出，在當前位置，在?6?的右邊比?6?小的數只有一個。 通過這樣的方法，每次把當前的數用線段樹進行個數統計，然后再計算出比它小的數即可。算法復雜度是?O(nlogm)。 * [ ] 樹狀數組（Fenwick Tree / Binary Indexed Tree） **實現** 舉例：假設有一個數組?array[0 … n-1]， 里面有?n?個元素，現在要經常對這個數組做兩件事。 1. 更新數組元素的數值 2. 求數組前?k?個元素的總和（或者平均值） * 解法 1：線段樹。 * 線段樹能在?O(logn)?的時間里更新和求解前?k?個元素的總和。 解法 2：樹狀數組。 * 該問題只要求求解前 k 個元素的總和，并不要求任意一個區間。 * 樹狀數組可以在?O(logn)?的時間里完成上述的操作。 * 相對于線段樹的實現，樹狀數組顯得更簡單。 特點 樹狀數組的數據結構有以下幾個重要的基本特征。 1. 它是利用數組來表示多叉樹的結構，在這一點上和優先隊列有些類似，只不過，優先隊列是用數組來表示完全二叉樹，而樹狀數組是多叉樹。 2. 樹狀數組的第一個元素是空節點。 3. 如果節點?tree[y]?是?tree[x]?的父節點，那么需要滿足條件：y =?x?- (x & (-x))。 建議：由于樹狀數組所解決的問題跟線段樹有些類似，所以不花篇幅進行問題的討論。LeetCode?上有很多經典的題目可以用樹狀數組來解決，比如?LeetCode?第?308?題，求一個動態變化的二維矩陣里，任意子矩陣里的數的總和。 #### 總結 這節課講解了一些高級的數據結構。 1. 優先隊列 經常出現在考題里的，它的實現過程比較繁瑣，但是很多編程語言里都有它的實現，所以在解決面試中的問題時，實行“拿來主義”即可。 鼓勵你自己練習實現一個優先隊列，在實現它的過程中更好地去了解它的結構和特點。 2. 圖 被廣泛運用的數據結構，很多涉及大數據的問題都得運用到圖論的知識。 比如在社交網絡里，每個人可以用圖的頂點表示，人與人直接的關系可以用圖的邊表示；再比如，在地圖上，要求解從起始點到目的地，如何行駛會更快捷，需要運用圖論里的最短路徑算法。 3. 前綴樹 出現在許多面試的難題當中。 因為很多時候你得自己實現一棵前綴樹，所以你要能熟練地書寫它的實現以及運用它。 4. 線段樹和樹狀數組 應用場合比較明確。 例如，問題變為在一幅圖片當中修改像素的顏色，然后求解任意矩形區間的灰度平均值，那么可以考慮采用二維的線段樹了。 建議：LeetCode 平臺上，針對上面的這些高級數據結構都有豐富的題目，希望你能用功學習。