1. 為什么把三個(gè)算法放在一講最近在整理經(jīng)典算法題精講系列這一講比較特殊把Manacher算法、bfprt算法、KMP算法放在了一起。乍一看這三個(gè)東西八竿子打不著——一個(gè)管回文串一個(gè)管TopK一個(gè)管字符串匹配。但把它們放一起講是有道理的因?yàn)樗鼈児蚕硗粋€(gè)核心命題如何把暴力解法優(yōu)化到線性復(fù)雜度。先從各自的戰(zhàn)場(chǎng)說(shuō)起。KMP算法解決的是字符串匹配問(wèn)題就是在一個(gè)長(zhǎng)文本里找一個(gè)模式串是否出現(xiàn)、出現(xiàn)在哪。暴力做法是拿模式串逐位對(duì)齊主串失配就右移一位重新比較最壞復(fù)雜度O(n*m)。KMP的精髓在于失配時(shí)不回退主串指針只利用已匹配部分的信息快速移動(dòng)模式串把匹配過(guò)程壓到O(nm)。Manacher算法解決的是最長(zhǎng)回文子串問(wèn)題。回文串是正著讀倒著讀都一樣的字符串比如aba、abba。暴力解法以每個(gè)字符為中心向兩邊擴(kuò)展復(fù)雜度O(n2)。Manacher利用回文的鏡像對(duì)稱性質(zhì)在擴(kuò)展過(guò)程中復(fù)用已經(jīng)算過(guò)的回文半徑信息把復(fù)雜度降到O(n)。bfprt算法解決的是無(wú)序數(shù)組中找第K小或第K大元素的問(wèn)題。常規(guī)思路是用快速排序的partition做隨機(jī)選擇期望O(n)但最壞退化到O(n2)。bfprt是一套確定性的選主元策略保證每次partition都能淘汰足夠多的元素從數(shù)學(xué)上證明最壞也是O(n)。這五個(gè)字母來(lái)自Blum、Floyd、Pratt、Rivest、Tarjan五位作者的名字所以也叫中位數(shù)的中位數(shù)算法。這三個(gè)算法在面試和競(jìng)賽中的出場(chǎng)率很高但很多人對(duì)它們的理解停留在背模板層面換個(gè)場(chǎng)景就懵。比如KMP的next數(shù)組求法江湖上有至少三種定義方式網(wǎng)上教程各寫(xiě)各的初學(xué)者很容易繞暈。比如Manacher的對(duì)稱性優(yōu)化邊界情況處理錯(cuò)一位整個(gè)結(jié)果就崩。再比如bfprt問(wèn)為什么必須是5個(gè)一組能答上來(lái)的人真不多大多數(shù)只是機(jī)械地照著代碼抄。這篇是先講KMP和Manacherbfprt的完整版本放在下一篇展開(kāi)。之所以這么安排是因?yàn)镵MP的next數(shù)組演示了信息復(fù)用這個(gè)思想的最基礎(chǔ)形態(tài)Manacher則在這個(gè)思想上加了一層對(duì)稱性的巧勁bfprt又把它延伸到確定性選主元的方向。三個(gè)算法放在一起看能明顯感受到算法優(yōu)化的一條主線想辦法利用已有的計(jì)算結(jié)果避免重復(fù)勞動(dòng)。下面先把KMP掰開(kāi)揉碎講清楚再講Manacher。整個(gè)過(guò)程我盡量用當(dāng)初我學(xué)的時(shí)候踩過(guò)的坑的視角來(lái)寫(xiě)配合完整的Java實(shí)現(xiàn)代碼最后附上刷題時(shí)常見(jiàn)的幾個(gè)問(wèn)題排查思路。2. KMP算法next數(shù)組是靈魂2.1 從BF算法到KMP到底優(yōu)化了什么先明確一點(diǎn)KMP解決的是單模式串匹配問(wèn)題。給定一個(gè)主串S和一個(gè)模式串P要在S中找到P第一次出現(xiàn)的位置。最原始的做法叫BF算法Brute Force也叫樸素匹配。BF的做法從S的每個(gè)位置i出發(fā)拿P逐位對(duì)齊比較。如果某一位失配就把P整體右移一位從P的第0位重新開(kāi)始比較。public static int bfSearch(String s, String p) { int n s.length(), m p.length(); for (int i 0; i m n; i) { int j 0; while (j m s.charAt(i j) p.charAt(j)) { j; } if (j m) { return i; } } return -1; }這段代碼邏輯沒(méi)錯(cuò)問(wèn)題出在效率上。假設(shè)S是aaaaaaaaaaaaaaaaabP是aaab每次都要比較到P的最后一位才發(fā)現(xiàn)失配然后i只前進(jìn)一位。整體下來(lái)近似比較nm次復(fù)雜度O(nm)。仔細(xì)想想BF到底浪費(fèi)了什么信息答案是已經(jīng)匹配成功的那一段被白白丟掉了。舉個(gè)例子SababcabcabababdPababd。當(dāng)P的前4位abab都匹配成功第5位P[4]d與主串中的c失配時(shí)我們能從這個(gè)4位已經(jīng)匹配的事實(shí)中推導(dǎo)出什么P的前綴abab有長(zhǎng)度為2的公共前后綴ab這意味著如果把P右移2位P的前綴ab依然能和主串當(dāng)前位置之前的ab對(duì)上。這個(gè)結(jié)論只需要分析P自己就能得到不需要知道主串的任何額外信息。KMP的核心思想就用一句話概括失配時(shí)利用模式串自身的結(jié)構(gòu)信息把模式串一次性右移到可能匹配的最遠(yuǎn)位置主串指針絕不回退。這里的模式串自身的結(jié)構(gòu)信息就是next數(shù)組。2.2 next數(shù)組的兩種定義方式別再混了網(wǎng)上講KMP的教程next數(shù)組的定義有無(wú)數(shù)種版本本質(zhì)都是最長(zhǎng)公共前后綴長(zhǎng)度但在具體實(shí)現(xiàn)上差一位。先明確一個(gè)基礎(chǔ)概念對(duì)于一個(gè)字符串它的前綴是去掉末尾若干字符后得到的子串后綴是去掉開(kāi)頭若干字符后得到的子串。所謂最長(zhǎng)公共前后綴就是既是前綴又是后綴的最長(zhǎng)子串長(zhǎng)度且這個(gè)子串不能是字符串本身也不能是空串。比如ababa長(zhǎng)度為1的前后綴a和a相等匹配長(zhǎng)度為1長(zhǎng)度為2的前后綴ab和ba不等長(zhǎng)度為3的前后綴aba和aba相等匹配長(zhǎng)度為3長(zhǎng)度為4的前后綴abab和baba不等所以ababa的最長(zhǎng)公共前后綴長(zhǎng)度是3。網(wǎng)上常見(jiàn)的next數(shù)組定義有兩種定義Anext[i]表示模式串P的[0, i)子串即P[0..i-1]的最長(zhǎng)公共前后綴長(zhǎng)度也就是中文教程里常說(shuō)的前綴函數(shù)。這里的next[0]-1有些約定為0表示空串沒(méi)有公共前后綴。定義Bnext[i]表示模式串P的[0, i]子串即P[0..i]的最長(zhǎng)公共前后綴長(zhǎng)度即next[i]對(duì)應(yīng)的是包含第i個(gè)字符在內(nèi)的子串。兩種定義各有擁護(hù)者計(jì)算出來(lái)的next數(shù)組整體錯(cuò)一位但匹配時(shí)的跳轉(zhuǎn)邏輯也相應(yīng)調(diào)整。KMP本身沒(méi)有歧義算法是正確的歧義全在next數(shù)組的具體約定上。這篇文章里我采用題目中給出的定義來(lái)規(guī)定next[i]定義為模式串p[0..i-1]的最長(zhǎng)公共前后綴長(zhǎng)度不過(guò)next[0]我習(xí)慣設(shè)為-1用-1作為公共前后綴不存在的哨兵。為了避免歧義下面直接用具體例子說(shuō)明。2.3 手算abacaba的next數(shù)組看題目里的例子模式串Pabacaba按照next[i]定義為p[0..i-1]的最長(zhǎng)公共前后綴長(zhǎng)度來(lái)計(jì)算。先拆開(kāi)看每個(gè)前綴子串i0: 空串next[0] -1 i1: p[0]a最長(zhǎng)公共前后綴長(zhǎng)度為0next[1] 0 i2: p[0..1]ab前綴a后綴b不等next[2] 0 i3: p[0..2]aba前綴a后綴a長(zhǎng)度1更長(zhǎng)的不行next[3] 1 i4: p[0..3]abaca和c不等next[4] 0 i5: p[0..4]abaca前綴a后綴a長(zhǎng)度1前綴ab和后綴ca不等next[5] 1 i6: p[0..5]abacab前綴ab后綴ab長(zhǎng)度2aba和cab不等next[6] 2 i7: p[0..6]abacaba前綴aba后綴aba長(zhǎng)度3next[7] 3所以得到i01234567next[i]-10010123這里的next[7]是最后用到的值嗎不一定。如果匹配到P最后一位失敗了需要跳轉(zhuǎn)到next[7]3也就是說(shuō)明前7位都匹配上了但第8位失配此時(shí)模式串最長(zhǎng)公共前后綴長(zhǎng)度為3所以從下標(biāo)3繼續(xù)嘗試。理解這個(gè)表之后再來(lái)看代碼實(shí)現(xiàn)。求next數(shù)組的代碼經(jīng)典寫(xiě)法如下public static int[] getNext(String p) { int m p.length(); int[] next new int[m 1]; next[0] -1; int i 0, j -1; while (i m) { if (j -1 || p.charAt(i) p.charAt(j)) { i; j; next[i] j; } else { j next[j]; } } return next; }這段代碼的核心邏輯是用兩個(gè)指針i和jj代表已經(jīng)匹配上的公共前后綴長(zhǎng)度。如果p[i]p[j]說(shuō)明公共前后綴可以延長(zhǎng)一位繼續(xù)如果失配j就回退到next[j]相當(dāng)于在計(jì)算next數(shù)組的過(guò)程中也要用到next數(shù)組自身的跳轉(zhuǎn)信息這就是遞歸地利用已計(jì)算的信息。有個(gè)細(xì)節(jié)值得注意next數(shù)組長(zhǎng)度是m1而不是m因?yàn)榘凑斩xAnext[m]是完整的P[0..m-1]的最長(zhǎng)公共前后綴長(zhǎng)度匹配過(guò)程中模式串走到頭時(shí)也要查這個(gè)值。2.4 KMP匹配過(guò)程主串指針不回退有了next數(shù)組匹配邏輯就順理成章了。public static int kmpSearch(String s, String p) { int n s.length(), m p.length(); if (m 0) return 0; int[] next getNext(p); int i 0, j 0; while (i n) { if (j -1 || s.charAt(i) p.charAt(j)) { i; j; } else { j next[j]; } if (j m) { return i - m; } } return -1; }匹配時(shí)最關(guān)鍵的跳轉(zhuǎn)分支是else當(dāng)s[i] ! p[j]時(shí)主串下標(biāo)i不動(dòng)只把模式串下標(biāo)j更新為next[j]。這里next[j]的含義是前j個(gè)字符已經(jīng)匹配相同時(shí)最長(zhǎng)公共前后綴的長(zhǎng)度所以模式串跳到該長(zhǎng)度處繼續(xù)比較而主串當(dāng)前位置之前的那些字符已經(jīng)保證與模式串前綴對(duì)齊了。用生活類比理解你在書(shū)里查找一個(gè)詞當(dāng)連續(xù)幾頁(yè)都符合關(guān)鍵詞前綴突然某一頁(yè)對(duì)不上時(shí)你不會(huì)回到書(shū)的第一頁(yè)重查而是根據(jù)已經(jīng)匹配到的部分把關(guān)鍵詞的某個(gè)前綴對(duì)齊到當(dāng)前頁(yè)繼續(xù)往后翻。主串就好比書(shū)頁(yè)只有前進(jìn)沒(méi)有后退模式串的移動(dòng)靠next數(shù)組來(lái)指導(dǎo)。來(lái)看一個(gè)具體的匹配例子。主串Sababacabacaba模式串Pabacaba。i0j0s[0]a與p[0]a匹配i1j1i1j1s[1]b與p[1]b匹配i2j2i2j2s[2]a與p[2]a匹配i3j3i3j3s[3]b與p[3]c失配j跳到next[3]1主串不前進(jìn)i3j1s[3]b與p[1]b匹配i4j2i4j2s[4]a與p[2]a匹配i5j3i5j3s[5]c與p[3]c匹配i6j4i6j4s[6]a與p[4]a匹配i7j5i7j5s[7]b與p[5]b匹配i8j6i8j6s[8]a與p[6]a匹配i9j7jm返回i-m2主串從位置2開(kāi)始匹配成功即子串a(chǎn)bacaba出現(xiàn)在S[2..8]位置。注意在第4步主串index3處的失配i沒(méi)有回退到1而是原地等待模式串通過(guò)next跳轉(zhuǎn)后繼續(xù)比較。這就是KMP主串不回退的直觀體現(xiàn)。KMP的時(shí)間復(fù)雜度為什么是O(nm)匹配過(guò)程中i只會(huì)增加不會(huì)減少最多增加n次j每次失配時(shí)通過(guò)next跳轉(zhuǎn)會(huì)變小但j增加的次數(shù)不超過(guò)i增加的次數(shù)每次匹配成功j加1匹配失敗j減少但總量有限整體均攤下來(lái)代價(jià)是線性的。求next數(shù)組同理i和j的移動(dòng)次數(shù)也是O(m)。所以最終是O(nm)。2.5 KMP的應(yīng)用遠(yuǎn)不止字符串匹配很多初學(xué)者覺(jué)得KMP只能用來(lái)做文本里的子串查找其實(shí)它的應(yīng)用面比想象中寬。第一個(gè)實(shí)用場(chǎng)景是判斷一個(gè)字符串是否是另一個(gè)字符串的循環(huán)移位。比如判斷B是否是A的循環(huán)移位常規(guī)思路是AA拼起來(lái)看B在AA中是否出現(xiàn)。這本質(zhì)就是一次KMP匹配。第二個(gè)場(chǎng)景是求字符串的最短重復(fù)周期。給一個(gè)字符串s如果它可以由某個(gè)子串重復(fù)k次構(gòu)成找出這個(gè)最小周期子串。結(jié)論是用KMP求出next數(shù)組后答案是n - next[n]如果n % (n - next[n]) 0那么這個(gè)最短重復(fù)周期長(zhǎng)度就是n - next[n]。這個(gè)結(jié)論在很多字符串題里是隱藏考點(diǎn)。第三個(gè)場(chǎng)景是KMP自動(dòng)機(jī)思想。把KMP的匹配過(guò)程理解成模式串在不同狀態(tài)之間跳轉(zhuǎn)這就是有限狀態(tài)自動(dòng)機(jī)的雛形。AC自動(dòng)機(jī)多模式串匹配、最大長(zhǎng)度前綴匹配等進(jìn)階算法都建立在這個(gè)思想上。所以說(shuō)KMP不是孤立的一個(gè)小技巧它是很多字符串?dāng)?shù)據(jù)結(jié)構(gòu)的底層地基。提示刷題時(shí)如果遇到判斷子串是否出現(xiàn)求最短周期循環(huán)移位這類描述第一反應(yīng)應(yīng)該是KMP或KMP的變形而不是直接上暴力。3. Manacher算法最長(zhǎng)回文子串的線性解法3.1 回文問(wèn)題的暴力解法為什么慢KMP講清楚了來(lái)看Manacher。這個(gè)算法解決的是最長(zhǎng)回文子串問(wèn)題比如給定字符串babad最長(zhǎng)回文子串是bab或aba長(zhǎng)度3。暴力解法有兩種思路。第一種是枚舉所有子串逐個(gè)判斷是否回文復(fù)雜度O(n3)基本屬于不可用。第二種是中心擴(kuò)展法枚舉每個(gè)位置作為回文中心向兩邊擴(kuò)展直到不能擴(kuò)展為止記錄最長(zhǎng)的回文長(zhǎng)度。public static String longestPalindrome(String s) { if (s null || s.length() 1) return ; int start 0, maxLen 1; for (int i 0; i s.length(); i) { int len1 expand(s, i, i); // 奇數(shù)長(zhǎng)度回文 int len2 expand(s, i, i 1); // 偶數(shù)長(zhǎng)度回文 int len Math.max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substring(start, start maxLen); } private static int expand(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } return right - left - 1; }中心擴(kuò)展法的時(shí)間復(fù)雜度是O(n2)在字符串長(zhǎng)度幾百萬(wàn)級(jí)別時(shí)完全跑不動(dòng)。Manacher算法的目標(biāo)是把復(fù)雜度壓到O(n)。它的核心優(yōu)化只有一條當(dāng)我們要計(jì)算某個(gè)位置的回文半徑時(shí)如果這個(gè)位置位于之前某個(gè)大回文的內(nèi)部那么可以利用回文的對(duì)稱性直接借用對(duì)稱位置的已知回文半徑作為初始值省去從1開(kāi)始擴(kuò)展的過(guò)程。3.2 鏡像對(duì)稱Manacher最巧妙的優(yōu)化要理解Manacher先弄明白四個(gè)變量C當(dāng)前已知的回文串的中心位置R當(dāng)前已知的回文串的最右邊界R右邊那個(gè)位置表示半徑覆蓋到R-1P[i]以位置i為中心的回文半徑包含中心本身mirror 2*C - ii關(guān)于C的對(duì)稱位置算法的核心邏輯是如果i在R的范圍內(nèi)即i R那么P[i]至少等于min(P[mirror], R - i)。為什么因?yàn)閕和mirror關(guān)于C對(duì)稱而C的回文范圍[R的左邊界, R]是對(duì)稱的。既然以C為中心的回文包含了i和mirror那么mirror回文半徑里的內(nèi)容在i的鏡像位置上一定也是對(duì)稱的。所以P[i]可以直接從P[mirror]繼承這是Manacher的加速核心。但有個(gè)限制條件P[i]不能超過(guò)R-i因?yàn)橐坏┏^(guò)R就超出了C的回文覆蓋范圍這個(gè)范圍之外的對(duì)稱性就無(wú)法保證了。所以取min(P[mirror], R - i)。如果i在R之外沒(méi)有對(duì)稱信息可用P[i]初始為1。這里有一個(gè)關(guān)鍵問(wèn)題回文半徑的奇偶性怎么處理回文串有兩種情況奇數(shù)長(zhǎng)度如aba中心是單個(gè)字符b偶數(shù)長(zhǎng)度如abba中心在bb之間。直接處理時(shí)需要區(qū)分兩種情況代碼寫(xiě)起來(lái)麻煩而且P數(shù)組在不同情況下含義不一致。Manacher的經(jīng)典做法是在原始字符串的每個(gè)字符之間包括首尾插入一個(gè)特殊字符比如把a(bǔ)ba改寫(xiě)成#a#b#a#把a(bǔ)bba改寫(xiě)成#a#b#b#a#。插入后原來(lái)的奇數(shù)回文和偶數(shù)回文都統(tǒng)一成了奇數(shù)回文以特殊字符為中心或普通字符為中心處理起來(lái)就不需要分支判斷了。這里的特殊字符可以是任何不沖突的字符比如#因?yàn)樗粫?huì)與原始字符匹配。原始字符串s長(zhǎng)度為n變換后的字符串t長(zhǎng)度為2n1。求得的P[i]是t中以i為中心的回文半徑對(duì)應(yīng)到原始字符串的回文長(zhǎng)度就是P[i]-1。最終答案就是所有P[i]中的最大值減1。3.3 Manacher的完整實(shí)現(xiàn)與邊界分析直接看代碼public static String manacher(String s) { if (s null || s.length() 0) return ; // 構(gòu)造帶分隔符的字符串 char[] chars new char[s.length() * 2 1]; int idx 0; for (int i 0; i chars.length; i) { chars[i] (i % 2 0) ? # : s.charAt(idx); } int n chars.length; int[] p new int[n]; int C 0, R 0; int maxLen 0, maxCenter 0; for (int i 0; i n; i) { // 利用對(duì)稱性初始化 p[i] if (i R) { int mirror 2 * C - i; p[i] Math.min(p[mirror], R - i); } else { p[i] 1; } // 中心擴(kuò)展 while (i - p[i] 0 i p[i] n chars[i - p[i]] chars[i p[i]]) { p[i]; } // 更新 C 和 R if (i p[i] R) { C i; R i p[i]; } // 記錄最大長(zhǎng)度 if (p[i] - 1 maxLen) { maxLen p[i] - 1; maxCenter i; } } // 根據(jù)中心位置還原原始字符串 int start (maxCenter - maxLen) / 2; return s.substring(start, start maxLen); }逐行拆解第一步構(gòu)造帶分隔符的數(shù)組。偶數(shù)位放#奇數(shù)位放原始字符注意chars[1]是s[0]chars[3]是s[1]以此類推。第二步初始化P[i]。當(dāng)i R時(shí)用對(duì)稱性預(yù)填一個(gè)初始值這樣while循環(huán)的擴(kuò)展次數(shù)被大大壓縮。當(dāng)i R時(shí)沒(méi)有對(duì)稱信息可用初始為1。第三步中心擴(kuò)展。這個(gè)while循環(huán)看起來(lái)和暴力中心擴(kuò)展一樣但它的執(zhí)行次數(shù)已經(jīng)被前面的初始化大幅削減。注意邊界條件i - p[i] 0 和 i p[i] n防止數(shù)組越界。第四步更新C和R。C和R的更新原則是一旦發(fā)現(xiàn)當(dāng)前位置的最右邊界超過(guò)了原來(lái)的R就更新R和C。這保證了后續(xù)位置盡量多的i能夠落在R的范圍內(nèi)從而利用鏡像優(yōu)化。第五步記錄最大長(zhǎng)度。maxLen p[i] - 1對(duì)應(yīng)原始字符串的回文長(zhǎng)度。還原原始字符串的下標(biāo)時(shí)有一個(gè)小技巧maxCenter是變換后數(shù)組中的中心下標(biāo)maxLen是原始回文長(zhǎng)度那么原始字符串起始位置是(maxCenter - maxLen) / 2。這個(gè)公式可以自己推一下變換后的字符到原始字符的下標(biāo)映射關(guān)系是rawIndex transformedIndex / 2因?yàn)椴迦胱址剂艘话胛恢没匚脑谧儞Q后數(shù)組中的區(qū)間是[maxCenter - maxLen, maxCenter maxLen]除2后對(duì)應(yīng)的原始區(qū)間起點(diǎn)就是(maxCenter - maxLen) / 2。3.4 復(fù)雜度分析和幾個(gè)容易踩的坑Manacher的復(fù)雜度為什么是O(n)看似while循環(huán)里有一層嵌套但是注意每次while擴(kuò)展都會(huì)使R向右移動(dòng)而R在整個(gè)算法過(guò)程中只會(huì)向右移動(dòng)最多移動(dòng)n次。所以while循環(huán)的總執(zhí)行次數(shù)是O(n)的。P數(shù)組的初始化、C和R的更新都是O(1)操作總的循環(huán)次數(shù)n次所以整體是O(n)。實(shí)際操作中有幾個(gè)坑我在這里集中說(shuō)一下第一個(gè)坑是分隔符的選擇。用#是慣例但要求這個(gè)字符不能出現(xiàn)在原始字符串里否則會(huì)干擾匹配。比如原始字符串里有#你還用#做分隔符整個(gè)算法的正確性就被破壞了。穩(wěn)妥做法是選一個(gè)不影響判斷的字符或者明確知道原始字符集范圍。第二個(gè)坑是P[i]的初始值。我見(jiàn)過(guò)很多人把p[i]初始化寫(xiě)成0然后while循環(huán)里從i開(kāi)始擴(kuò)展這樣就會(huì)漏掉單個(gè)字符的回文情況導(dǎo)致邊界問(wèn)題。記住p[i]至少是1因?yàn)閱蝹€(gè)字符本身是回文。第三個(gè)坑是還原原始字符串下標(biāo)時(shí)容易算錯(cuò)。直接用原始思路推導(dǎo)會(huì)快很多別死記公式推一遍就懂。第四個(gè)坑是C和R的更新時(shí)機(jī)。只有當(dāng)i p[i] R時(shí)才更新等于不更新。因?yàn)榈扔诘臅r(shí)候新的回文半徑?jīng)]有超出已有覆蓋范圍不需要調(diào)整。注意Manacher求的是最長(zhǎng)回文子串的長(zhǎng)度或者具體子串。如果題目只需要長(zhǎng)度可以精簡(jiǎn)掉字符串還原部分只保留maxLen的計(jì)算。Manacher在高頻面試題中的出現(xiàn)率很高尤其是字節(jié)、快手的算法題庫(kù)里最長(zhǎng)回文子串幾乎是標(biāo)配題用Manacher寫(xiě)成O(n)級(jí)別面試官的印象分會(huì)比O(n2)高不少。4. bfprt算法確定性搞定TopK問(wèn)題4.1 TopK問(wèn)題為什么難在最壞情況前兩個(gè)算法都講完了最后說(shuō)bfprt。整體安排在下一篇展開(kāi)但核心思路和代碼框架值得先在這里鋪墊一下方便大家把三個(gè)算法串起來(lái)理解。問(wèn)題定義給定一個(gè)無(wú)序數(shù)組找出第K小或第K大的元素。比如[3, 2, 1, 5, 6, 4]K2時(shí)答案是2排序后為[1,2,3,4,5,6]第2小是2。最簡(jiǎn)單的做法是排序后取第K個(gè)復(fù)雜度O(n log n)。但這個(gè)問(wèn)題比排序更簡(jiǎn)單不需要完全有序所以期望做到O(n)。常見(jiàn)的優(yōu)化方案是快速選擇QuickSelect利用快速排序的partition思想每次選取一個(gè)pivot把數(shù)組分成小于pivot和大于pivot兩部分。如果pivot的位置恰好是K直接返回否則在左半邊或右半邊遞歸。隨機(jī)選pivot時(shí)期望復(fù)雜度是O(n)但最壞情況下每次選到最大或最小元素遞歸規(guī)模每次只減少1復(fù)雜度退化為O(n2)。bfprt算法要解決的就是這個(gè)最壞情況它通過(guò)一種確定性的pivot選擇策略保證無(wú)論輸入數(shù)據(jù)長(zhǎng)什么樣復(fù)雜度都能控制在O(n)。4.2 中位數(shù)的中位數(shù)五個(gè)一組的原因bfprt的核心是中位數(shù)的中位數(shù)選主元思路整個(gè)過(guò)程分五步將數(shù)組按每5個(gè)元素一組分組最后一組不足5個(gè)也單獨(dú)成組對(duì)每組內(nèi)的元素排序組內(nèi)最多5個(gè)用插入排序即可取出每組的中位數(shù)放到一個(gè)新的數(shù)組中遞歸調(diào)用bfprt求這個(gè)中位數(shù)數(shù)組的中位數(shù)把它作為pivot用pivot對(duì)原數(shù)組做partition根據(jù)partition后的位置判斷是在左邊找還是在右邊找遞歸處理為什么必須是5個(gè)一組這是bfprt算法中最核心的證明點(diǎn)。假設(shè)數(shù)組有n個(gè)元素5個(gè)一組共有n/5組近似。每組內(nèi)部排序后取中位數(shù)由于每組有5個(gè)元素中位數(shù)是第3個(gè)即每組有2個(gè)元素小于等于該組中位數(shù)2個(gè)元素大于等于。這些中位數(shù)的中位數(shù)記為pivot。那么有多少元素能確定小于pivot有一半的組的中位數(shù)小于等于pivot因?yàn)閜ivot是中位數(shù)的中位數(shù)這些組各有2個(gè)元素小于等于該組中位數(shù)所以這些組的至少3個(gè)元素小于等于pivot該組中位數(shù)本身加上2個(gè)更小的。粗略估算有約(n/10)*3 3n/10個(gè)元素一定小于pivot。同理約3n/10個(gè)元素一定大于pivot。所以partition之后最壞情況下遞歸處理的子問(wèn)題規(guī)模不超過(guò)7n/10。由此得到遞歸式T(n) ≤ T(n/5) T(7n/10) O(n)其中T(n/5)是求中位數(shù)的中位數(shù)的時(shí)間T(7n/10)是遞歸查找的時(shí)間O(n)是分組、排序、partition的時(shí)間。解這個(gè)遞歸式最終得到T(n) O(n)。用替代法可以直接證明。為什么不用3個(gè)一組3個(gè)一組的話每組中位數(shù)以上的元素有2個(gè)有一半組的中位數(shù)小于pivot所以能確定小于pivot的元素約(n/6)*2 n/3遞歸規(guī)模變?yōu)?n/3遞歸式變?yōu)門(mén)(n) ≤ T(n/3) T(2n/3) O(n)這個(gè)式子解出來(lái)是O(n log n)無(wú)法保證線性。7個(gè)一組可以但分組排序的常數(shù)更大實(shí)際運(yùn)行更慢。5個(gè)一組是數(shù)學(xué)證明和工程效率的平衡點(diǎn)。4.3 bfprt的確定性為什么重要bfprt相對(duì)QuickSelect的優(yōu)勢(shì)是確定性。QuickSelect依賴隨機(jī)性雖然期望復(fù)雜度是O(n)但在某些特定輸入下比如數(shù)組已經(jīng)有序且每次pivot都選到最小值會(huì)退化。bfprt不依賴數(shù)據(jù)分布無(wú)論輸入什么都能保證O(n)。但是這里要說(shuō)不中聽(tīng)的話bfprt的常數(shù)特別大每次遞歸都要分組、組內(nèi)排序、求中位數(shù)數(shù)組的中位數(shù)實(shí)際運(yùn)行時(shí)間可能比QuickSelect慢好幾倍。所以它在工程中很少直接使用更多是作為理論工具出現(xiàn)。比如在算法課上證明選擇問(wèn)題存在確定性線性算法或者在某些實(shí)時(shí)系統(tǒng)里要求最壞情況可控的場(chǎng)景。面試中如果被問(wèn)到建議這樣回答先說(shuō)bfprt是確定性O(shè)(n)的TopK算法再說(shuō)五步流程最后強(qiáng)調(diào)5個(gè)一組的原因——保證每次partition至少刪除3n/10個(gè)元素遞歸規(guī)模最多7n/10最終解出O(n)。完整代碼實(shí)現(xiàn)、變種問(wèn)題和復(fù)雜度的嚴(yán)格數(shù)學(xué)證明我放在下一篇寫(xiě)。這里先給出一個(gè)簡(jiǎn)單的Java框架方便對(duì)照理解public static int bfprt(int[] arr, int k) { // k從1開(kāi)始計(jì)數(shù) return bfprt(arr, 0, arr.length - 1, k - 1); } private static int bfprt(int[] arr, int left, int right, int k) { if (left right) return arr[left]; int pivot medianOfMedians(arr, left, right); int[] range partition(arr, left, right, pivot); if (k range[0] k range[1]) { return arr[k]; } else if (k range[0]) { return bfprt(arr, left, range[0] - 1, k); } else { return bfprt(arr, range[1] 1, right, k); } }這里的medianOfMedians對(duì)應(yīng)上面說(shuō)的選主元邏輯partition是荷蘭國(guó)旗問(wèn)題的三路快排寫(xiě)法。等下篇再展開(kāi)。5. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄5.1 KMP next數(shù)組求錯(cuò)的排查思路KMP寫(xiě)出來(lái)跑一遍結(jié)果不對(duì)90%的情況是next數(shù)組求錯(cuò)了。排查時(shí)按以下步驟走第一步對(duì)照你采用的next定義手算幾個(gè)簡(jiǎn)單串的結(jié)果比如aaaa、abab、abcabc看看你的代碼輸出是什么。如果手算和代碼不一致說(shuō)明理解或?qū)崿F(xiàn)有一方出了問(wèn)題。第二步重點(diǎn)檢查求next的循環(huán)邊界。while循環(huán)的終止條件、i和j的初始值、next[i]賦值時(shí)機(jī)這三處最容易錯(cuò)。比如忘了next[0]-1或者在失配時(shí)回退j寫(xiě)成j--而不是jnext[j]都會(huì)導(dǎo)致結(jié)果偏差。第三步打印匹配過(guò)程的中間變量。在kmpSearch的else分支里打印i和j的值觀察主串指針是否真的沒(méi)有回退模式串跳轉(zhuǎn)是否和手算一致。我見(jiàn)過(guò)一個(gè)典型錯(cuò)誤定義A和定義B混用。求next時(shí)用定義Anext[i]p[0..i-1]的最長(zhǎng)公共前后綴但匹配跳轉(zhuǎn)時(shí)卻按定義B的邏輯來(lái)。雖然只是差一位但最終的匹配結(jié)果完全不對(duì)。5.2 Manacher邊界問(wèn)題排查Manacher代碼不長(zhǎng)但邊界問(wèn)題非常隱蔽。如果你發(fā)現(xiàn)結(jié)果差一位或者偶數(shù)字符串處理錯(cuò)先檢查以下幾點(diǎn)第一檢查構(gòu)造的變換數(shù)組是否正確。下標(biāo)0放#下標(biāo)1放s[0]下標(biāo)3放s[1]這個(gè)映射錯(cuò)了整個(gè)算法全崩。可以先打印變換后的字符數(shù)組肉眼核對(duì)。第二檢查while循環(huán)的邊界條件。i - p[i] 0和i p[i] n這兩個(gè)條件缺一不可少寫(xiě)一個(gè)就會(huì)數(shù)組越界。第三檢查還原回文子串的公式。之前提到start (maxCenter - maxLen) / 2這里maxCenter是變換后數(shù)組的下標(biāo)maxLen是原始回文長(zhǎng)度。如果你用p[i]直接當(dāng)作原始長(zhǎng)度還原出的字符串就是錯(cuò)的。第四檢查空串和單字符的邊界情況?？沾苯臃祷乜諉巫址祷刈陨磉@兩個(gè)case要單獨(dú)處理。5.3 面試中的常見(jiàn)追問(wèn)與應(yīng)對(duì)思路這三個(gè)算法在面試中只會(huì)寫(xiě)代碼是不夠的很可能被追問(wèn)到原理層面的問(wèn)題。對(duì)于KMP面試官最常問(wèn)的是next數(shù)組怎么來(lái)的為什么時(shí)間復(fù)雜度是O(n)next[j]回退時(shí)為什么不會(huì)漏掉可能的匹配回答時(shí)抓住主串指針不回退和利用模式串自身的最長(zhǎng)公共前后綴信息這兩個(gè)核心就行。對(duì)于Manacher高頻追問(wèn)是為什么插入分隔符后能統(tǒng)一奇偶為什么P[i]的初始值取min(P[mirror], R-i)復(fù)雜度的直觀解釋是什么回答時(shí)記得強(qiáng)調(diào)超過(guò)R的部分對(duì)稱性無(wú)法保證所以必須取min這個(gè)關(guān)鍵點(diǎn)。對(duì)于bfprt高頻追問(wèn)是為什么是5個(gè)一組3個(gè)一組行不行怎么證明復(fù)雜度是O(n)回答時(shí)把遞歸式和分組淘汰比例講清楚基本就能過(guò)。還有一個(gè)小技巧面試時(shí)如果寫(xiě)了bfprt可以先說(shuō)一句這個(gè)算法常數(shù)比較大實(shí)際工程中通常用隨機(jī)化QuickSelect但bfprt的優(yōu)勢(shì)是確定性O(shè)(n)。這句話能體現(xiàn)你對(duì)算法有整體認(rèn)知而不僅僅是背了模板。6. 三個(gè)算法的共同主線把KMP、Manacher、bfprt放一起講完再回頭看它們的聯(lián)系。KMP的next數(shù)組是利用已匹配部分的公共前后綴信息避免主串回退Manacher的P數(shù)組是利用回文的鏡像對(duì)稱性避免重復(fù)擴(kuò)展bfprt是分組取中位數(shù)再取中位數(shù)的中位數(shù)避免partition選到極端pivot。三個(gè)算法從不同的角度驗(yàn)證了同一個(gè)道理算法優(yōu)化的本質(zhì)是信息的最大化復(fù)用以及最壞情況的主動(dòng)規(guī)避。這個(gè)道理應(yīng)用到實(shí)際開(kāi)發(fā)中很多性能問(wèn)題都能找到優(yōu)化思路。比如處理字符串時(shí)如果發(fā)現(xiàn)某些子串被反復(fù)計(jì)算就要考慮預(yù)處理記憶化處理大數(shù)據(jù)時(shí)如果某種選主元策略在極端輸入下會(huì)退化就要考慮更穩(wěn)妥的確定性策略。下一篇會(huì)展開(kāi)bfprt的完整實(shí)現(xiàn)包括每組排序代碼、中位數(shù)數(shù)組的遞歸處理、partition的三路劃分以及幾個(gè)變種題目第K大、找中位數(shù)、找出所有TopK元素的解法。到時(shí)候拿到代碼建議先自己跑一遍再試著改一改比單純看一遍印象深得多。我自己帶過(guò)的學(xué)員里很多人卡在這三個(gè)算法上是因?yàn)檠鄹呤值汀粗v解都覺(jué)得懂了一寫(xiě)代碼就各種邊界問(wèn)題。所以這里多說(shuō)一句算法這東西看一百遍不如手寫(xiě)五遍寫(xiě)完再對(duì)著測(cè)試用例跑尤其要把剛才說(shuō)的邊界情況全部測(cè)一遍。這個(gè)過(guò)程不是浪費(fèi)時(shí)間而是真正把別人的解法變成自己的內(nèi)功。