第08講：高頻真題解析 I · 300分鐘搞定數據結構與算法

從這節課開始，我們將一起分析 LeetCode 里面的高頻題。這些題目都非常具有代表性，是各大公司面試的高頻題，因為它們可以考察大家對問題的剖析能力，解決問題的方案是否完善，以及代碼的書寫功底。這節課主要介紹的解題方法是： * 線性法及優化線性法 * 切分法 * 快速選擇算法 * 最小堆法 * 分治法 #### 例題分析一 LeetCode 第 03 題：給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例 1 ``` 輸入："abcabcbb" 輸出：3 ``` 解釋：因為無重復字符的最長子串是"abc"，其長度為3。示例 2 ``` 輸入："bbbbb" 輸出：1 ``` 解釋：因為無重復字符的最長子串是 "b"，其長度為 1。示例 3 ``` 輸入："pwwkew" 輸出：3 ``` 解釋：因為無重復字符的最長子串是 "wke"，其長度為 3。 > 注意：答案必須是子串的長度，"pwke" 是一個子序列，不是子串。 * [ ] 解題思路一：暴力法 ? ? ? ?? ? ? ? 找出所有的子串，然后一個一個地去判斷每個子串里是否包含有重復的字符。假設字符串的長度為 n，那么有 n×(n + 1) / 2 個非空子串。計算過程如下。 ``` 長度為 1 的子串，有 n 個長度為 2 的子串，每兩個每兩個相鄰地取，一共有 n - 1 個長度為 3 的子串，每三個每三個相鄰地取，一共有 n - 2 個 …… 以此類推，長度為 k 的子串，有 n - k + 1 個。 ``` 當 k 等于 n 的時候，n - k + 1=1，即長度為 n 的子串有 1 個。所有情況相加，得到所有子串的長度為： ``` n + (n - 1) + (n - 2) + (n - 3) + … + 2 + 1 = n×(n + 1) / 2 ``` 算上空字符串，那么就一共有 n×(n + 1) / 2 + 1 個。拓展一下，對于一個長度為 n 的字符串，一共有多少個子序列呢？和子串不一樣，子序列里的元素不需要相互挨著。同理分析，長度為 1 的子序列有 n 個，即 Cn1，長度為 2 的子序列個數為 Cn2，以此類推，長度為 k 的子序列有?Cnk，那么所有子序列的個數（包括空序列）是?Cn0?+ Cn1?+ Cn2?+ … Cnn?= 2n 注意：對于統計子串和子序列個數的方法和結果，大家務必記下來，對于在分析各種問題時會有很大幫助。回到本來問題，如果對所有的子串進行判斷，從每個子串里尋找出最長的那個并且沒有重復字符的，那么復雜度就是：O(n×(n + 1)/2×n) = O(n3)。 * [ ] 解題思路二：線性法 * 例題 1：給定的字符串里有一段是沒有重復字符的，如下，能不能把下一個字符 a 加進來？要看當前的子串”abc”是否已經包含了字符 a。掃描一遍“abc”，當發現某個字符與 a 相同，可以得出結論。把“abc“三個字符放入到一個哈希集合里，那么就能在 O(1) 的時間里作出判斷，提高速度。使用定義一個哈希集合 set 的方法，從給定字符串的頭開始，每次檢查一下當前字符是不是在集合里邊，如果不在，說明這個字符不會造成重復和沖突，把它加入到集合里，并統計一下當前集合的長度，可能它就是最長的那個子串。 * 例題 2：如果發現新的字符已經在集合里已經出現了，怎么辦？ deabc 是目前為止沒有重復字符的最長子串，當我們遇到下一個字符a的時候，以這個字符結尾的沒有重復的子串是“bca”，而此時集合里的字符有：d，e，a，b，c。首先，必須把 a 刪除，因為這樣才能把新的 a 加入到集合里，那么如何判斷要把 d 和 e 也都刪除呢？ 1. 可以定義兩個指針 i 和 j。 2. i 是慢指針，j 是快指針，當 j 遇到了一個重復出現的字符時，從慢指針開始一個一個地將 i 指針指向的字符從集合里刪除，然后判斷一下是否可以把新字符加入到集合里而不會產生重復。 3. 把字符 d 刪除后，i 指針向前移動一步，此時集合里還剩下：e, a, b, c，很明顯，字符 a 還在集合里，仍然要繼續刪除。 4. 把字符 e 刪除后，集合里還剩 a，b，c，字符 a 還在集合里，繼續刪除慢指針 i 指向的字符 a。 5. 集合里剩 b，c，可以放心地把新的字符 a 放入到集合里，然后快指針 j 往前移動一步。通過這樣不斷嘗試，每當新的字符加入到集合里的時候，統計一下當前集合里的元素個數，最后記錄下最長的那個。 * 時間復雜度由于采用的是快慢指針的策略，字符串最多被遍歷兩次，快指針遇到的字符會被添加到哈希集合，而慢指針遇到的字符會從哈希集合里刪除，對哈希集合的操作都是 O(1) 的時間復雜度，因此，整個算法的時間復雜度就是?n×O(1) + n×O(1) = O(n)。 * 空間復雜度由于用到了一個哈希集合，在最壞的情況下，給定的字符串沒有任何重復的字符，需要把每個字符都加入到哈希集合里，因此空間復雜度是 O(n)。代碼實現 ``` // 定義一個哈希集合 set，初始化結果 max 為 0 int lengthOfLongestSubstring(String s) { ? ?Set<Character> set = new HashSet<>(); ? ?int max = 0; ? ?// 用快慢指針 i 和 j 掃描一遍字符串，如果快指針所指向的字符已經出現在哈希集合里，不斷地嘗試將慢指針所指向的字符從哈希集合里刪除 ? ?for (int i = 0, j = 0; j < s.length(); j++) { ? ? ? ?while (set.contains(s.charAt(j))) { ? ? ? ? ? ?set.remove(s.charAt(i)); ? ? ? ? ? ?i++; ? ? ? ?} ? ? ? ? ? ? ? ?// 當快指針的字符加入到哈希集合后，更新一下結果 max ? ? ? ?set.add(s.charAt(j)); ? ? ? ?max = Math.max(max, set.size()); ? ?} ? ?return max; } ``` * [ ] 解題思路三：優化的線性法在上述例題中，能否讓慢指針不再一步一步地挪動，而是迅速地跳到字符 b 的位置？可以用哈希表來記錄每個字符以及它出現的位置，當遇到了字符 a 的時候，就知道跟它重復的前一個字符出現的位置，只需要讓慢指針指向那個位置的下一個即可。（如果題目說所有字符都是字母的話，也可以用一個數組去記錄。）遇到字符 a，此時哈希表的記錄 {d: 0, e: 1, a: 2, b: 3: c: 4}，a 的位置是 2，把 2 加上 1 等于 3，就能讓慢指針 i 指向下標為 3 的位置，即 b 字符的地方。? ? ? ? > 注意：在運用這個算法的時候，不能去數哈希集合的元素個數來作為子串的長度，所以得額外維護一個變量來保存最后的結果。但是在一些情況下，我們不能簡單地將取出來的重復位置加 1，如下：快指針 j 指向的字符是 e，而 e 在哈希表里記錄的位置是 1。? 在這種情況下，沒有必要讓 i 重新指向 e 后面的 a。此時，i 應該保留在原地不動。因此，i 被移動到的新位置應該等于 max(i，重復字符出現位置 + 1）。代碼實現 ``` //?定義一個哈希表用來記錄上一次某個字符出現的位置，并初始化結果?max?為?0 int?lengthOfLongestSubstring(String?s)?{ ????Map<Character,?Integer>?map?=?new?HashMap<>(); ????int?max?=?0; ????//?用快慢指針?i?和?j?掃描一遍字符串，若快指針所對應的字符已經出現過，則慢指針跳躍 ????for?(int?i?=?0,?j?=?0;?j?<?s.length();?j++)?{ ????????if?(map.containsKey(s.charAt(j)))?{ ????????????i?=?Math.max(i,?map.get(s.charAt(j))?+?1); ????????} ???????? ????????map.put(s.charAt(j),?j); ????????max?=?Math.max(max,?j?-?i?+?1); ????} ???? ????return?max; } ``` #### 例題分析二 LeetCode?第 04 題：給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為 O(log(m+n))。你可以假設 nums1 和 nums2 不會同時為空。 * 示例1 ``` nums1 = [1, 3] nums2 = [2] ``` 則中位數是 2.0 * 示例2 ``` nums1 = [1, 2] nums2 = [3, 4] ``` 則中位數是 (2 + 3)/2 = 2.5 * [ ] 解題思路一：暴力法因為兩個數組都是排好序的，可以利用歸并排序將它們合并成一個長度為 m+n 的有序數組，合并的時間復雜度是 m+n，然后從中選取中位數，整體的時間復雜度就是 O(m+n)。這是比較直觀的解法，但是比題目要求的 O(log(m+n)) 慢了許多，并不適合。 * [ ] 解題思路二：切分法假設 m+n = L，若 L 為奇數，即兩個數組的元素總個數為奇數，那么它們的中位數就是第 int(L / 2) + 1 小的數。例如，數組 { 1, 2, 3 } 的中位數是 2，2 就是第二小的數 2 = int(3/2) + 1。如果 L 是偶數，那么中位數就是第 int(L/2) 小與第 int(L/2)+1 小的數的和的平均值。例如，數組 {1, 2, 3, 4} 的中位數是 (2 + 3) / 2 = 2.5，其中，2 = int(4/2)，3 = int(4/2) + 1。因此這個問題就轉變為在兩個有序數組中尋找第 k 小的數 f(k)，當 L 是奇數的時候，另 k = L/2，結果為 f(k + 1)；而當 L 是偶數的時候，結果為 f(k) + f(k + 1) / 2。 * 如何從兩個排好序的數組里找出第 k 小的數？假設我們從第一個數組里前面 k1?個數，從第二個數組里取出前面 k2?個數，如下圖。假設 k = 5，k1?= 3，k2?= 2，有下面幾種情況。 1. 當 a2?= b1?時，可以肯定??a2?和?b1?就是第 5 小的數。因為當把 a0、a1、a2?以及 b0、b1?按照大小順序合并在一起的時候，?a2?和?b1?一定排在最后面，完全不需要考慮 a0、a1?和 b0?的大小關系。其中一種可能的排列如下。 2. 當 a2?< b1?的時候，無法肯定 a2?和 b1?是不是第 5 小的數。舉例如下。? ? ? ?? 而最終第 5 小的數是 a3?5 這個數。因此，在這種情況下，我們不能得出第 5 小的數是哪個。但是，在這種情況下，至少我們可以肯定的是，我們要找的結果肯定不會在 a0，a1，a2?之間，即不會出現在 nums1 數組的前半段里。為什么呢？很簡單，因為如果第 5 小的數是 a0，a1，a2?其中一個的話，意味著 k1+k2?必然大于 5，這就跟我們的假設不符了。那么結果會不會在 nums2 的后半段呢？不可能，加入第 5 小的數在 nums2 的后半段，那么意味著，這個數要大于 b1（即 ?7），也會大于 a2（即 3），但是 k1?+ k2?已經等于 5了，所以就和假設沖突了。在這樣的情況下，我們可以把搜索的范圍縮小，從 nums1 的后半段以及 nums2 的前半段中繼續尋找。當 a2?> b1?的時候，無法肯定 a2?和 b1?是不是第 5 小的數。舉例如下。 ``` nums1[] = {5, 6,?7, 8, 9} nums2[] = {1,?2, 3, 4} a2?= 7，b1?= 2 ``` 而最終第 5 小的數是 a0?5 這個數。因此，在這種情況下，我們也不能得出第 5 小的數是哪個。但是，在這種情況下，至少我們可以肯定的是，我們要找的結果肯定不會是 b0，或者nums2 數組的前半段里。為什么呢？因為如果第 5 小的數是 b0 的話，意味著 k1+k2 必然大于 5，這也跟我們的假設不符了。同樣的，結果也不可能在 nums1 的后半段里。在這樣的情況下，我們可以把搜索的范圍縮小，從 nums2 的后半段以及 nums1 中繼續尋找。代碼實現 ``` double?findMedianSortedArrays(int?nums1[],?int?nums2[])?{ ????int?m?=?nums1.length; ????int?n?=?nums2.length; ?? ????int?k?=?(m?+?n)?/?2; ?? ????if?((m?+?n)?%?2?==?1)?{ ????????return?findKth(nums1,?0,?m?-?1,?nums2,?0,?n?-?1,?k?+?1); ??????}?else?{ ????????return?( ????????????findKth(nums1,?0,?m?-?1,?nums2,?0,?n?-?1,?k)?+? ????????????findKth(nums1,?0,?m?-?1,?nums2,?0,?n?-?1,?k?+?1) ????????)?/?2.0; ????} } double?findKth(int[]?nums1,?int?l1,?int?h1,?int[]?nums2,?int?l2,?int?h2,?int?k)?{ ????int?m?=?h1?-?l1?+?1; ????int?n?=?h2?-?l2?+?1; ?? ????if?(m?>?n)?{ ????????return?findKth(nums2,?l2,?h2,?nums1,?l1,?h1,?k); ????} ?? ????if?(m?==?0)?{ ????????return?nums2[l2?+?k?-?1]; ????} ?? ????if?(k?==?1)?{ ????????return?Math.min(nums1[l1],?nums2[l2]); ????} ?? ????int?na?=?Math.min(k/2,?m); ????int?nb?=?k?-?na; ????int?va?=?nums1[l1?+?na?-?1]; ????int?vb?=?nums2[l2?+?nb?-?1]; ?? ????if?(va?==?vb)?{ ????????return?va; ????}?else?if?(va?<?vb)?{ ????????return?findKth(nums1,?l1?+?na,?h1,?nums2,?l2,?l2?+?nb?-?1,?k?-?na); ????}?else?{ ???????return?findKth(nums1,?l1,?l1?+?na?-?1,?nums2,?l2?+?nb,?h2,?k?-?nb); ????} ?? } ``` 1. 主體函數其實就是根據兩個字符串長度的總和進行判斷，看看如何調用遞歸函數以及返回結果。當總長度是奇數的時候，返回正中間的那個數；當總長度是偶數的時候，返回中間兩個數的平均值。 2. 進入 findkth 函數，這個函數的目的是尋找第 k 小的元素。 3. 如果 nums1 數組的長度大于 nums2 數組的長度，我們將它們互換一下，這樣可以讓程序結束得快一些。 4. 當 nums1 的長度為 0 時，直接返回 nums2 數組里第 k 小的數。當 k 等于 1 的時候，返回兩個數組中的最小值。 5. 接下來，分別選兩個數組的中間數。 6. 比較一下兩者的大小，如果相等，表明我們找到了中位數，返回它；如果不等的話，我們進行剪枝處理。 * [ ] 算法分析由于要求中位數，即 k = (m+n) / 2，k1 = k / 2，k2 = k / 2，每次都能將一半的數排除，即問題的規模減小一半，因此，算法復雜度就類似二分搜索，復雜度就是 log(k)，即?O(log((m+n) / 2))。 **擴展一** 例題：如果給定的兩個數組是沒有經過排序處理的，應該怎么找出中位數呢？ **解法 1：直觀方法** 先將兩個數組合并在一起，然后排序，再選出中位數。時間復雜度是：O((m+n)× og(m+n))。 **解法 2：快速選擇算法** 快速選擇算法，可以在 O(n) 的時間內從長度為 n 的沒有排序的數組中取出第 k 小的數，運用了快速排序的思想。假如將 nums1[] 與 nums2[] 數組組合成一個數組變成 nums[]：{2, 5, 3, 1, 6, 8, 9, 7, 4}，那么如何在這個沒有排好序的數組中找到第 k 小的數呢？ 1. 隨機地從數組中選擇一個數作為基準值，比如 7。一般而言，隨機地選擇基準值可以避免最壞的情況出現。 2. 將數組排列成兩個部分，以基準值作為分界點，左邊的數都小于基準值，右邊的都大于基準值。? ?? 3. 判斷一下基準值所在位置 p：如果 p 剛好等于 k，那么基準值就是所求數，直接返回。如果 k < p，即基準值太大，搜索的范圍應該縮小到基準值的左邊。如果 k > p，即基準值太小，搜索的范圍應該縮小到基準值的右邊。此時需要找的應該是第 k - p 小的數，因為前 p 個數被淘汰。 4. 重復第一步，直到基準值的位置 p 剛好就是要找的 k。代碼實現 ``` public?int?findKthLargest(int[]?nums,?int?k)?{ ????return?quickSelect(nums,?0,?nums.length?-?1,?k); } //?隨機取一個基準值，這里取最后一個數作為基準值 int?quickSelect(int[]?nums,?int?low,?int?high,?int?k)?{ ????int?pivot?=?low; ????//?比基準值小的數放左邊，把比基準值大的數放右邊 ????for?(int?j?=?low;?j?<?high;?j++)?{ ??????if?(nums[j]?<=?nums[high])?{ ??????????swap(nums,?pivot++,?j); ??????} ????} ????swap(nums,?pivot,?high); ?? ????//?判斷基準值的位置是不是第?k?大的元素 ????int?count?=?high?-?pivot?+?1; ????//?如果是，就返回結果。 ????if?(count?==?k)?return?nums[pivot]; ????//?如果發現基準值小了，繼續往右邊搜索 ????if?(count?>?k)?return?quickSelect(nums,?pivot?+?1,?high,?k); ????//?如果發現基準值大了，就往左邊搜索 ????return?quickSelect(nums,?low,?pivot?-?1,?k?-?count); ?? } ``` **時間復雜度** 時間復雜度為什么是 O(n)。分析如下。為了方便推算，假設每次都選擇中間的那個數作為基準值。設函數的時間執行函數為 T(n)，第一次運行的時候，把基準值和所有的 n 個元素進行比較，然后將輸入規模減半并遞歸，所以 T(n) = T(n/2) + n。當規模減半后，新的基準值只和 n/2 個元素進行比較，因此 T(n/2) = T(n/4) + n/2。以此類推： ``` T(n/4) = T(n/8) + n/4 … T(2) = T(1) + 2 T(1) = 1 ``` 將上面的公式逐個代入后得到 T(n) = 1 + 2 + … + n/8 + n/4 + n/2 + n = 2×n，所以 ?O(T(n)) = O(n)。 **空間復雜度** 如果不考慮遞歸對棧的開銷，那么算法并沒有使用額外的空間，swap 操作都是直接在數組里完成，因此空間復雜度為 O(1)。 **解法 3：數組“組合”** 把這兩個數組“虛擬”地組合在一起，即它們是分開的，但是在訪問它們的元素時，把它們看成是一個數組。那么就能運用快速選擇的算法。代碼實現 ``` double?findMedianArrays(int[]?nums1,?int[]?nums2)?{ ????int?m?=?nums1.length; ????int?n?=?nums2.length; ?? ????int?k?=?(m?+?n)?/?2; ?? ????return?(m?+?n)?%?2?==?1?? ????????findKthLargest(nums1,?nums2,?k?+?1)?: ????????(findKthLargest(nums1,?nums2,?k)?+?findKthLargest(nums1,?nums2,?k?+?1))?/?2.0; } double?findKthLargest(int[]?nums1,?int[]?nums2,?int?k)?{ ????return?quickSelect(nums1,?nums2,?0,?nums1.length?+?nums2.length?-?1,?k); } double?quickSelect(int[]?nums1,?int[]?nums2,?int?low,?int?high,?int?k)?{ ????int?pivot?=?low; ????//?use?quick?sort's?idea ????//?put?nums?that?are?<=?pivot?to?the?left ????//?put?nums?that?are??>?pivot?to?the?right ????for?(int?j?=?low;?j?<?high;?j++)?{ ????????if?(getNum(nums1,?nums2,?j)?<=?getNum(nums1,?nums2,?high))?{ ????????????swap(nums1,?nums2,?pivot++,?j); ????????} ????} ????swap(nums1,?nums2,?pivot,?high); ?? ????//?count?the?nums?that?are?>?pivot?from?high ????int?count?=?high?-?pivot?+?1; ????//?pivot?is?the?one! ????if?(count?==?k)?return?getNum(nums1,?nums2,?pivot); ????//?pivot?is?too?small,?so?it?must?be?on?the?right ????if?(count?>?k)?return?quickSelect(nums1,?nums2,?pivot?+?1,?high,?k); ????//?pivot?is?too?big,?so?it?must?be?on?the?left ????return?quickSelect(nums1,?nums2,?low,?pivot?-?1,?k?-?count); } int?getNum(int[]?nums1,?int[]?nums2,?int?index)?{ ????return?(index?<?nums1.length)???nums1[index]?:?nums2[index?-?nums1.length]; } void?swap(int[]?nums1,?int[]?nums2,?int?i,?int?j)?{ ????int?m?=?nums1.length; ?? ????if?(i?<?m?&&?j?<?m)?{ ????????swap(nums1,?i,?j); ????}?else?if?(i?>=?m?&&?j?>=?m)?{ ????????swap(nums2,?i?-?m,?j?-?m); ????}?else?if?(i?<?m?&&?j?>=?m)?{ ????????int?temp?=?nums1[i]; ????????nums1[i]?=?nums2[j?-?m]; ????????nums2[j?-?m]?=?temp; ????} } void?swap(int[]?nums,?int?i,?int?j)?{ ????int?temp?=?nums[i]; ????nums[i]?=?nums[j]; ????nums[j]?=?temp; } ``` 因為這道題的解法與之前講的快速選擇算法非常類似，差別在于將兩個數組合在一起考慮。因此大家可以自己分析一下代碼。時間復雜度是 O(m+n)，空間復雜度 O(1)。擴展二例題：有一萬個服務器，每個服務器上存儲了十億個沒有排好序的數，現在要找所有數當中的中位數，怎么找？對于分布式地大數據處理，應當考慮兩個方面的限制： * 每臺服務器進行算法計算的復雜度限制，包括時間和空間復雜度 * 服務器與服務器之間進行通信時的網絡帶寬限制 **限制 1：空間復雜度** 假設存儲的數都是 32 位整型，即 4 個字節，那么 10 億個數需占用 40 億字節，大約 4GB 歸并排序至少得需要 4GB 的內存快速排序的空間復雜度為 log(n)，即大約 30 次堆棧壓入用非遞歸的方法去實現快速排序，代碼如下。 ``` //?每次只需將數組中的某個起始點和終點，即一個范圍，壓入堆棧中，壓入?30?個范圍的大小約為?30×2×4=240?字節 class?Range?{ ????public?int?low; ????public?int?high; ?? ????public?Range(int?low,?int?high)?{ ????????this.low?=?low; ????????this.high?=?high; ????} } //?不使用遞歸寫法，壓入堆棧的還包括程序中的其他變量等，假設需要?100?字節，總共需要?30×100=3K?字節 void?quickSort(int[]?nums)?{ ????Stack<Range>?stack?=?new?Stack<>(); ????Range?range?=?new?Range(0,?nums.length?-?1); ????stack.push(range); ?? ????while?(!stack.isEmpty())?{ ????????range?=?stack.pop(); ???? ????????int?pivot?=?partition(nums,?range.low,?range.high); ???? ????????if?(pivot?-?1?>?range.low)?{ ????????????stack.push(new?Range(range.low,?pivot?-?1)); ????????} ???? ????????if?(pivot?+?1?<?range.high)?{ ????????????stack.push(new?Range(pivot?+?1,?range.high)); ????????} ????} } //?快速排序對內存的開銷非常小 int?partition(int[]?nums,?int?low,?int?high)?{ ????int?pivot?=?randRange(low,?high),?i?=?low; ????swap(nums,?pivot,?high); ?? ????for?(int?j?=?low;?j?<?high;?j++)?{ ????????if?(nums[j]?<=?nums[high])?{ ????????????swap(nums,?i++,?j); ????????} ????} ?? ????swap(nums,?i,?high); ?? ????return?i; } ``` 如上，利用一個棧 stack 來記錄每次進行快速排序時的范圍。一旦發現基準值左邊還有未處理完的數，就將左邊的范圍區間壓入到棧里；如果發現基準值右邊還有未處理完的數，就將右邊的范圍區間壓入到棧里。其中，處理基準值的 partition 函數非常重要，之前已經介紹過。 **限制 2：網絡帶寬** 在實際應用中，這是最重要的考量因素，很多大型的云服務器都是按照流量來進行收費，如何有效地限制流量，避免過多的服務器之間的通信，就是要考量的重點，并且，實際上它與算法的時間復雜度有很大的關系。解決方案借助擴展一的思路。 1. 從 1萬個服務器中選擇一個作為主機（master server）。這臺主機將扮演主導快速選擇算法的角色。? ? ? 2. 在主機上隨機選擇一個基準值，然后廣播到其他各個服務器上。 3. 每臺服務器都必須記錄下最后小于、等于或大于基準值數字的數量：less count，equal count，greater count。 4. 每臺服務器將 less count，equal count 以及 greater count 發送回主機。 5. 主機統計所有的 less count，equal count 以及 greater count，得出所有比基準值小的數的總和 total less count，等于基準值的總和 total equal count，以及大于基準值的總和 total greater count。進行如下判斷。 * 如果 total less count >= total count / 2，表明基準值太大。 * 如果total less count + total equal count >= total count / 2，表明基準值即為所求結果。 * 否則，total less count + total equal count < total count / 2 表明基準值太小。 6. 后面兩種情況，主機會把新的基準值廣播給各個服務器，服務器根據新的基準值的大小判斷往左半邊或者右半邊繼續進行快速選擇。直到最后找到中位數。 **時間復雜度** 整體的時間復雜度是 O(nlog(n))，主機和各個其他服務器之間的通信總共也需要 nlog(n)次，每次通信需要傳遞一個基準值以及三個計數值。如果用一些組播網絡（Multicast Network)，可以有效地節省更多的帶寬。 #### 例題分析三 LeetCode 第 23 題：合并 k 個排好序的鏈表，返回合并后的排序鏈表。分析和描述算法的復雜度。示例輸入： ``` [ ??1 -> 4 -> 5, ??1 -> 3 -> 4, ??2 -> 6 ] ``` 輸出：`1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6` * [ ] 解題思路一：暴力法用一個數組保存所有鏈表中的數，然后對這個數組進行排序，再從頭到尾將數組遍歷一遍，生成一個排好序的鏈表。假設每個鏈表的平均長度為 n，整體的時間復雜度就是 O(nk×log(nk))。 * [ ] 解題思路二：最小堆法面對 k 個排好序的鏈表時，最小的那個數肯定是從這 k 個鏈表的頭里面選出來。那么，第二小的如何選擇？例如，有下面 k 個鏈表。? ? ? ?? ? ? ? 1. 把最小的 1 從所有的 k 個鏈表頭里選出來之后，把 1 從鏈表里刪掉。 2. 下一個最小的數，還是從所有的 k 個鏈表頭里選出來。 3. 以此類推，每一輪都比較 k 個新的鏈表頭的大小，得出最后的結果。上述操作的時間復雜度是 O(k)。而針對找出最小的數，可以使用最小堆來提高效率。時間復雜度計算如下。 1. 對 k 個鏈表頭創建一個大小為 k 的最小堆，在第 2 課中提到創建一個大小為 k 的最小堆所需的時間是 O(k)； 2. 從堆里取出最小的數，都是 O(lg(k))； 3. 若每個鏈表的平均長度為 n，一共有 nk 個元素，即用大小為 k 的最小堆去過濾 nk 個元素； 4. 整體的時間復雜度就是 O(nk×log(k))。維護這個大小為 k 的最小堆，直到遍歷完所有 k 個鏈表里的所有元素。代碼實現 ``` public?ListNode?mergeKLists(ListNode[]?lists)?{ ????//利用一個空的鏈表頭方便插入節點。?? ????ListNode?fakeHead?=?new?ListNode(0),?p?=?fakeHead; ????int?k?=?lists.length; ?? ????//?定義一個最小堆來保存?k?個鏈表節點；將?k?個鏈表的頭放入到最小堆里。 ????PriorityQueue<ListNode>?heap?=? ????????new?PriorityQueue<>(k,?new?Comparator<ListNode>()?{ ????????????public?int?compare(ListNode?a,?ListNode?b)?{ ????????????????return?a.val?-?b.val; ????????????} ????????}); ????//?從最小堆里將當前最小的節點取出，插入到結果鏈表中。 ????for?(int?i?=?0;?i?<?k;?i++)?{ ????????if?(lists[i]?!=?null)?{ ????????????heap.offer(lists[i]); ????????} ????} ????while?(!heap.isEmpty())?{ ????????ListNode?node?=?heap.poll(); ???? ????????p.next?=?node; ????????p?=?p.next; ???? ????????//?如果發現該節點后面還有后續節點，將后續節點加入到最小堆里。???? ????????if?(node.next?!=?null)?{ ????????????heap.offer(node.next); ????????} ????} ????return?fakeHead.next; ?? } ``` * [ ] 解題思路三：分治法當 k=1 的時候，直接返回結果；當 k=2 的時候，把這兩個鏈表歸并。當 k=3 的時候，我們可以把它們分成兩組，分別歸并完畢后再進行最后的歸并操作，如下。上述做法運用了典型的分治思想，非常類似歸并排序操作。代碼實現 ``` public?ListNode?mergeKLists(ListNode[]?lists,?int?low,?int?high)?{ ????if?(low?==?high)?return?lists[low]; ?? ????int?middle?=?low?+?(high?-?low)?/?2;?//?從中間切一刀 ?? ????return?mergeTwoLists( ????????mergeKLists(lists,?low,?middle), ????????mergeKLists(lists,?middle?+?1,?high) ????);?//?遞歸地處理左邊和右邊的鏈表，最后合并 } public?ListNode?mergeTwoLists(ListNode?a,?ListNode?b)?{ ????if?(a?==?null)?return?b; ????if?(b?==?null)?return?a; ?? ????if?(a.val?<=?b.val)?{ ????????a.next?=?mergeTwoLists(a.next,?b); ????????return?a; ????} ?? ????b.next?=?mergeTwoLists(a,?b.next); ????return?b; } ``` 合并兩個排好序的鏈表非常簡單，此處使用遞歸函數，可以嘗試非遞歸寫法。 * 時間復雜度：O(nk×log(k))。 * 空間復雜度：O(1)。因為不像最小堆解法那樣需要維護一個額外的數據結構。 > 提示：因為這道題針對的是鏈表，所以很多操作都直接在鏈表上進行。 #### 結語這節課剖析了三道非常經典的高頻題，從不同的角度考慮解決問題的方案，并回顧了經典的快速選擇算法。下節課將討論另外三道經典的高頻題。