1. 为什么把三个算法放在一讲最近在整理经典算法题精讲系列这一讲比较特殊把Manacher算法、bfprt算法、KMP算法放在了一起。乍一看这三个东西八竿子打不着——一个管回文串一个管TopK一个管字符串匹配。但把它们放一起讲是有道理的因为它们共享同一个核心命题如何把暴力解法优化到线性复杂度。先从各自的战场说起。KMP算法解决的是字符串匹配问题就是在一个长文本里找一个模式串是否出现、出现在哪。暴力做法是拿模式串逐位对齐主串失配就右移一位重新比较最坏复杂度O(n*m)。KMP的精髓在于失配时不回退主串指针只利用已匹配部分的信息快速移动模式串把匹配过程压到O(nm)。Manacher算法解决的是最长回文子串问题。回文串是正着读倒着读都一样的字符串比如aba、abba。暴力解法以每个字符为中心向两边扩展复杂度O(n²)。Manacher利用回文的镜像对称性质在扩展过程中复用已经算过的回文半径信息把复杂度降到O(n)。bfprt算法解决的是无序数组中找第K小或第K大元素的问题。常规思路是用快速排序的partition做随机选择期望O(n)但最坏退化到O(n²)。bfprt是一套确定性的选主元策略保证每次partition都能淘汰足够多的元素从数学上证明最坏也是O(n)。这五个字母来自Blum、Floyd、Pratt、Rivest、Tarjan五位作者的名字所以也叫中位数的中位数算法。这三个算法在面试和竞赛中的出场率很高但很多人对它们的理解停留在背模板层面换个场景就懵。比如KMP的next数组求法江湖上有至少三种定义方式网上教程各写各的初学者很容易绕晕。比如Manacher的对称性优化边界情况处理错一位整个结果就崩。再比如bfprt问为什么必须是5个一组能答上来的人真不多大多数只是机械地照着代码抄。这篇是先讲KMP和Manacherbfprt的完整版本放在下一篇展开。之所以这么安排是因为KMP的next数组演示了信息复用这个思想的最基础形态Manacher则在这个思想上加了一层对称性的巧劲bfprt又把它延伸到确定性选主元的方向。三个算法放在一起看能明显感受到算法优化的一条主线想办法利用已有的计算结果避免重复劳动。下面先把KMP掰开揉碎讲清楚再讲Manacher。整个过程我尽量用当初我学的时候踩过的坑的视角来写配合完整的Java实现代码最后附上刷题时常见的几个问题排查思路。2. KMP算法next数组是灵魂2.1 从BF算法到KMP到底优化了什么先明确一点KMP解决的是单模式串匹配问题。给定一个主串S和一个模式串P要在S中找到P第一次出现的位置。最原始的做法叫BF算法Brute Force也叫朴素匹配。BF的做法从S的每个位置i出发拿P逐位对齐比较。如果某一位失配就把P整体右移一位从P的第0位重新开始比较。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; }这段代码逻辑没错问题出在效率上。假设S是aaaaaaaaaaaaaaaaabP是aaab每次都要比较到P的最后一位才发现失配然后i只前进一位。整体下来近似比较nm次复杂度O(nm)。仔细想想BF到底浪费了什么信息答案是已经匹配成功的那一段被白白丢掉了。举个例子SababcabcabababdPababd。当P的前4位abab都匹配成功第5位P[4]d与主串中的c失配时我们能从这个4位已经匹配的事实中推导出什么P的前缀abab有长度为2的公共前后缀ab这意味着如果把P右移2位P的前缀ab依然能和主串当前位置之前的ab对上。这个结论只需要分析P自己就能得到不需要知道主串的任何额外信息。KMP的核心思想就用一句话概括失配时利用模式串自身的结构信息把模式串一次性右移到可能匹配的最远位置主串指针绝不回退。这里的模式串自身的结构信息就是next数组。2.2 next数组的两种定义方式别再混了网上讲KMP的教程next数组的定义有无数种版本本质都是最长公共前后缀长度但在具体实现上差一位。先明确一个基础概念对于一个字符串它的前缀是去掉末尾若干字符后得到的子串后缀是去掉开头若干字符后得到的子串。所谓最长公共前后缀就是既是前缀又是后缀的最长子串长度且这个子串不能是字符串本身也不能是空串。比如ababa长度为1的前后缀a和a相等匹配长度为1长度为2的前后缀ab和ba不等长度为3的前后缀aba和aba相等匹配长度为3长度为4的前后缀abab和baba不等所以ababa的最长公共前后缀长度是3。网上常见的next数组定义有两种定义Anext[i]表示模式串P的[0, i)子串即P[0..i-1]的最长公共前后缀长度也就是中文教程里常说的前缀函数。这里的next[0]-1有些约定为0表示空串没有公共前后缀。定义Bnext[i]表示模式串P的[0, i]子串即P[0..i]的最长公共前后缀长度即next[i]对应的是包含第i个字符在内的子串。两种定义各有拥护者计算出来的next数组整体错一位但匹配时的跳转逻辑也相应调整。KMP本身没有歧义算法是正确的歧义全在next数组的具体约定上。这篇文章里我采用题目中给出的定义来规定next[i]定义为模式串p[0..i-1]的最长公共前后缀长度不过next[0]我习惯设为-1用-1作为公共前后缀不存在的哨兵。为了避免歧义下面直接用具体例子说明。2.3 手算abacaba的next数组看题目里的例子模式串Pabacaba按照next[i]定义为p[0..i-1]的最长公共前后缀长度来计算。先拆开看每个前缀子串i0: 空串next[0] -1 i1: p[0]a最长公共前后缀长度为0next[1] 0 i2: p[0..1]ab前缀a后缀b不等next[2] 0 i3: p[0..2]aba前缀a后缀a长度1更长的不行next[3] 1 i4: p[0..3]abaca和c不等next[4] 0 i5: p[0..4]abaca前缀a后缀a长度1前缀ab和后缀ca不等next[5] 1 i6: p[0..5]abacab前缀ab后缀ab长度2aba和cab不等next[6] 2 i7: p[0..6]abacaba前缀aba后缀aba长度3next[7] 3所以得到i01234567next[i]-10010123这里的next[7]是最后用到的值吗不一定。如果匹配到P最后一位失败了需要跳转到next[7]3也就是说明前7位都匹配上了但第8位失配此时模式串最长公共前后缀长度为3所以从下标3继续尝试。理解这个表之后再来看代码实现。求next数组的代码经典写法如下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; }这段代码的核心逻辑是用两个指针i和jj代表已经匹配上的公共前后缀长度。如果p[i]p[j]说明公共前后缀可以延长一位继续如果失配j就回退到next[j]相当于在计算next数组的过程中也要用到next数组自身的跳转信息这就是递归地利用已计算的信息。有个细节值得注意next数组长度是m1而不是m因为按照定义Anext[m]是完整的P[0..m-1]的最长公共前后缀长度匹配过程中模式串走到头时也要查这个值。2.4 KMP匹配过程主串指针不回退有了next数组匹配逻辑就顺理成章了。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; }匹配时最关键的跳转分支是else当s[i] ! p[j]时主串下标i不动只把模式串下标j更新为next[j]。这里next[j]的含义是前j个字符已经匹配相同时最长公共前后缀的长度所以模式串跳到该长度处继续比较而主串当前位置之前的那些字符已经保证与模式串前缀对齐了。用生活类比理解你在书里查找一个词当连续几页都符合关键词前缀突然某一页对不上时你不会回到书的第一页重查而是根据已经匹配到的部分把关键词的某个前缀对齐到当前页继续往后翻。主串就好比书页只有前进没有后退模式串的移动靠next数组来指导。来看一个具体的匹配例子。主串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主串不前进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开始匹配成功即子串abacaba出现在S[2..8]位置。注意在第4步主串index3处的失配i没有回退到1而是原地等待模式串通过next跳转后继续比较。这就是KMP主串不回退的直观体现。KMP的时间复杂度为什么是O(nm)匹配过程中i只会增加不会减少最多增加n次j每次失配时通过next跳转会变小但j增加的次数不超过i增加的次数每次匹配成功j加1匹配失败j减少但总量有限整体均摊下来代价是线性的。求next数组同理i和j的移动次数也是O(m)。所以最终是O(nm)。2.5 KMP的应用远不止字符串匹配很多初学者觉得KMP只能用来做文本里的子串查找其实它的应用面比想象中宽。第一个实用场景是判断一个字符串是否是另一个字符串的循环移位。比如判断B是否是A的循环移位常规思路是AA拼起来看B在AA中是否出现。这本质就是一次KMP匹配。第二个场景是求字符串的最短重复周期。给一个字符串s如果它可以由某个子串重复k次构成找出这个最小周期子串。结论是用KMP求出next数组后答案是n - next[n]如果n % (n - next[n]) 0那么这个最短重复周期长度就是n - next[n]。这个结论在很多字符串题里是隐藏考点。第三个场景是KMP自动机思想。把KMP的匹配过程理解成模式串在不同状态之间跳转这就是有限状态自动机的雏形。AC自动机多模式串匹配、最大长度前缀匹配等进阶算法都建立在这个思想上。所以说KMP不是孤立的一个小技巧它是很多字符串数据结构的底层地基。提示刷题时如果遇到判断子串是否出现求最短周期循环移位这类描述第一反应应该是KMP或KMP的变形而不是直接上暴力。3. Manacher算法最长回文子串的线性解法3.1 回文问题的暴力解法为什么慢KMP讲清楚了来看Manacher。这个算法解决的是最长回文子串问题比如给定字符串babad最长回文子串是bab或aba长度3。暴力解法有两种思路。第一种是枚举所有子串逐个判断是否回文复杂度O(n³)基本属于不可用。第二种是中心扩展法枚举每个位置作为回文中心向两边扩展直到不能扩展为止记录最长的回文长度。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); // 奇数长度回文 int len2 expand(s, i, i 1); // 偶数长度回文 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; }中心扩展法的时间复杂度是O(n²)在字符串长度几百万级别时完全跑不动。Manacher算法的目标是把复杂度压到O(n)。它的核心优化只有一条当我们要计算某个位置的回文半径时如果这个位置位于之前某个大回文的内部那么可以利用回文的对称性直接借用对称位置的已知回文半径作为初始值省去从1开始扩展的过程。3.2 镜像对称Manacher最巧妙的优化要理解Manacher先弄明白四个变量C当前已知的回文串的中心位置R当前已知的回文串的最右边界R右边那个位置表示半径覆盖到R-1P[i]以位置i为中心的回文半径包含中心本身mirror 2*C - ii关于C的对称位置算法的核心逻辑是如果i在R的范围内即i R那么P[i]至少等于min(P[mirror], R - i)。为什么因为i和mirror关于C对称而C的回文范围[R的左边界, R]是对称的。既然以C为中心的回文包含了i和mirror那么mirror回文半径里的内容在i的镜像位置上一定也是对称的。所以P[i]可以直接从P[mirror]继承这是Manacher的加速核心。但有个限制条件P[i]不能超过R-i因为一旦超过R就超出了C的回文覆盖范围这个范围之外的对称性就无法保证了。所以取min(P[mirror], R - i)。如果i在R之外没有对称信息可用P[i]初始为1。这里有一个关键问题回文半径的奇偶性怎么处理回文串有两种情况奇数长度如aba中心是单个字符b偶数长度如abba中心在bb之间。直接处理时需要区分两种情况代码写起来麻烦而且P数组在不同情况下含义不一致。Manacher的经典做法是在原始字符串的每个字符之间包括首尾插入一个特殊字符比如把aba改写成#a#b#a#把abba改写成#a#b#b#a#。插入后原来的奇数回文和偶数回文都统一成了奇数回文以特殊字符为中心或普通字符为中心处理起来就不需要分支判断了。这里的特殊字符可以是任何不冲突的字符比如#因为它不会与原始字符匹配。原始字符串s长度为n变换后的字符串t长度为2n1。求得的P[i]是t中以i为中心的回文半径对应到原始字符串的回文长度就是P[i]-1。最终答案就是所有P[i]中的最大值减1。3.3 Manacher的完整实现与边界分析直接看代码public static String manacher(String s) { if (s null || s.length() 0) return ; // 构造带分隔符的字符串 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) { // 利用对称性初始化 p[i] if (i R) { int mirror 2 * C - i; p[i] Math.min(p[mirror], R - i); } else { p[i] 1; } // 中心扩展 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]; } // 记录最大长度 if (p[i] - 1 maxLen) { maxLen p[i] - 1; maxCenter i; } } // 根据中心位置还原原始字符串 int start (maxCenter - maxLen) / 2; return s.substring(start, start maxLen); }逐行拆解第一步构造带分隔符的数组。偶数位放#奇数位放原始字符注意chars[1]是s[0]chars[3]是s[1]以此类推。第二步初始化P[i]。当i R时用对称性预填一个初始值这样while循环的扩展次数被大大压缩。当i R时没有对称信息可用初始为1。第三步中心扩展。这个while循环看起来和暴力中心扩展一样但它的执行次数已经被前面的初始化大幅削减。注意边界条件i - p[i] 0 和 i p[i] n防止数组越界。第四步更新C和R。C和R的更新原则是一旦发现当前位置的最右边界超过了原来的R就更新R和C。这保证了后续位置尽量多的i能够落在R的范围内从而利用镜像优化。第五步记录最大长度。maxLen p[i] - 1对应原始字符串的回文长度。还原原始字符串的下标时有一个小技巧maxCenter是变换后数组中的中心下标maxLen是原始回文长度那么原始字符串起始位置是(maxCenter - maxLen) / 2。这个公式可以自己推一下变换后的字符到原始字符的下标映射关系是rawIndex transformedIndex / 2因为插入字符占了一半位置回文在变换后数组中的区间是[maxCenter - maxLen, maxCenter maxLen]除2后对应的原始区间起点就是(maxCenter - maxLen) / 2。3.4 复杂度分析和几个容易踩的坑Manacher的复杂度为什么是O(n)看似while循环里有一层嵌套但是注意每次while扩展都会使R向右移动而R在整个算法过程中只会向右移动最多移动n次。所以while循环的总执行次数是O(n)的。P数组的初始化、C和R的更新都是O(1)操作总的循环次数n次所以整体是O(n)。实际操作中有几个坑我在这里集中说一下第一个坑是分隔符的选择。用#是惯例但要求这个字符不能出现在原始字符串里否则会干扰匹配。比如原始字符串里有#你还用#做分隔符整个算法的正确性就被破坏了。稳妥做法是选一个不影响判断的字符或者明确知道原始字符集范围。第二个坑是P[i]的初始值。我见过很多人把p[i]初始化写成0然后while循环里从i开始扩展这样就会漏掉单个字符的回文情况导致边界问题。记住p[i]至少是1因为单个字符本身是回文。第三个坑是还原原始字符串下标时容易算错。直接用原始思路推导会快很多别死记公式推一遍就懂。第四个坑是C和R的更新时机。只有当i p[i] R时才更新等于不更新。因为等于的时候新的回文半径没有超出已有覆盖范围不需要调整。注意Manacher求的是最长回文子串的长度或者具体子串。如果题目只需要长度可以精简掉字符串还原部分只保留maxLen的计算。Manacher在高频面试题中的出现率很高尤其是字节、快手的算法题库里最长回文子串几乎是标配题用Manacher写成O(n)级别面试官的印象分会比O(n²)高不少。4. bfprt算法确定性搞定TopK问题4.1 TopK问题为什么难在最坏情况前两个算法都讲完了最后说bfprt。整体安排在下一篇展开但核心思路和代码框架值得先在这里铺垫一下方便大家把三个算法串起来理解。问题定义给定一个无序数组找出第K小或第K大的元素。比如[3, 2, 1, 5, 6, 4]K2时答案是2排序后为[1,2,3,4,5,6]第2小是2。最简单的做法是排序后取第K个复杂度O(n log n)。但这个问题比排序更简单不需要完全有序所以期望做到O(n)。常见的优化方案是快速选择QuickSelect利用快速排序的partition思想每次选取一个pivot把数组分成小于pivot和大于pivot两部分。如果pivot的位置恰好是K直接返回否则在左半边或右半边递归。随机选pivot时期望复杂度是O(n)但最坏情况下每次选到最大或最小元素递归规模每次只减少1复杂度退化为O(n²)。bfprt算法要解决的就是这个最坏情况它通过一种确定性的pivot选择策略保证无论输入数据长什么样复杂度都能控制在O(n)。4.2 中位数的中位数五个一组的原因bfprt的核心是中位数的中位数选主元思路整个过程分五步将数组按每5个元素一组分组最后一组不足5个也单独成组对每组内的元素排序组内最多5个用插入排序即可取出每组的中位数放到一个新的数组中递归调用bfprt求这个中位数数组的中位数把它作为pivot用pivot对原数组做partition根据partition后的位置判断是在左边找还是在右边找递归处理为什么必须是5个一组这是bfprt算法中最核心的证明点。假设数组有n个元素5个一组共有n/5组近似。每组内部排序后取中位数由于每组有5个元素中位数是第3个即每组有2个元素小于等于该组中位数2个元素大于等于。这些中位数的中位数记为pivot。那么有多少元素能确定小于pivot有一半的组的中位数小于等于pivot因为pivot是中位数的中位数这些组各有2个元素小于等于该组中位数所以这些组的至少3个元素小于等于pivot该组中位数本身加上2个更小的。粗略估算有约(n/10)*3 3n/10个元素一定小于pivot。同理约3n/10个元素一定大于pivot。所以partition之后最坏情况下递归处理的子问题规模不超过7n/10。由此得到递归式T(n) ≤ T(n/5) T(7n/10) O(n)其中T(n/5)是求中位数的中位数的时间T(7n/10)是递归查找的时间O(n)是分组、排序、partition的时间。解这个递归式最终得到T(n) O(n)。用替代法可以直接证明。为什么不用3个一组3个一组的话每组中位数以上的元素有2个有一半组的中位数小于pivot所以能确定小于pivot的元素约(n/6)*2 n/3递归规模变为2n/3递归式变为T(n) ≤ T(n/3) T(2n/3) O(n)这个式子解出来是O(n log n)无法保证线性。7个一组可以但分组排序的常数更大实际运行更慢。5个一组是数学证明和工程效率的平衡点。4.3 bfprt的确定性为什么重要bfprt相对QuickSelect的优势是确定性。QuickSelect依赖随机性虽然期望复杂度是O(n)但在某些特定输入下比如数组已经有序且每次pivot都选到最小值会退化。bfprt不依赖数据分布无论输入什么都能保证O(n)。但是这里要说不中听的话bfprt的常数特别大每次递归都要分组、组内排序、求中位数数组的中位数实际运行时间可能比QuickSelect慢好几倍。所以它在工程中很少直接使用更多是作为理论工具出现。比如在算法课上证明选择问题存在确定性线性算法或者在某些实时系统里要求最坏情况可控的场景。面试中如果被问到建议这样回答先说bfprt是确定性O(n)的TopK算法再说五步流程最后强调5个一组的原因——保证每次partition至少删除3n/10个元素递归规模最多7n/10最终解出O(n)。完整代码实现、变种问题和复杂度的严格数学证明我放在下一篇写。这里先给出一个简单的Java框架方便对照理解public static int bfprt(int[] arr, int k) { // k从1开始计数 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对应上面说的选主元逻辑partition是荷兰国旗问题的三路快排写法。等下篇再展开。5. 常见问题与排查技巧实录5.1 KMP next数组求错的排查思路KMP写出来跑一遍结果不对90%的情况是next数组求错了。排查时按以下步骤走第一步对照你采用的next定义手算几个简单串的结果比如aaaa、abab、abcabc看看你的代码输出是什么。如果手算和代码不一致说明理解或实现有一方出了问题。第二步重点检查求next的循环边界。while循环的终止条件、i和j的初始值、next[i]赋值时机这三处最容易错。比如忘了next[0]-1或者在失配时回退j写成j--而不是jnext[j]都会导致结果偏差。第三步打印匹配过程的中间变量。在kmpSearch的else分支里打印i和j的值观察主串指针是否真的没有回退模式串跳转是否和手算一致。我见过一个典型错误定义A和定义B混用。求next时用定义Anext[i]p[0..i-1]的最长公共前后缀但匹配跳转时却按定义B的逻辑来。虽然只是差一位但最终的匹配结果完全不对。5.2 Manacher边界问题排查Manacher代码不长但边界问题非常隐蔽。如果你发现结果差一位或者偶数字符串处理错先检查以下几点第一检查构造的变换数组是否正确。下标0放#下标1放s[0]下标3放s[1]这个映射错了整个算法全崩。可以先打印变换后的字符数组肉眼核对。第二检查while循环的边界条件。i - p[i] 0和i p[i] n这两个条件缺一不可少写一个就会数组越界。第三检查还原回文子串的公式。之前提到start (maxCenter - maxLen) / 2这里maxCenter是变换后数组的下标maxLen是原始回文长度。如果你用p[i]直接当作原始长度还原出的字符串就是错的。第四检查空串和单字符的边界情况。空串直接返回空单字符返回自身这两个case要单独处理。5.3 面试中的常见追问与应对思路这三个算法在面试中只会写代码是不够的很可能被追问到原理层面的问题。对于KMP面试官最常问的是next数组怎么来的为什么时间复杂度是O(n)next[j]回退时为什么不会漏掉可能的匹配回答时抓住主串指针不回退和利用模式串自身的最长公共前后缀信息这两个核心就行。对于Manacher高频追问是为什么插入分隔符后能统一奇偶为什么P[i]的初始值取min(P[mirror], R-i)复杂度的直观解释是什么回答时记得强调超过R的部分对称性无法保证所以必须取min这个关键点。对于bfprt高频追问是为什么是5个一组3个一组行不行怎么证明复杂度是O(n)回答时把递归式和分组淘汰比例讲清楚基本就能过。还有一个小技巧面试时如果写了bfprt可以先说一句这个算法常数比较大实际工程中通常用随机化QuickSelect但bfprt的优势是确定性O(n)。这句话能体现你对算法有整体认知而不仅仅是背了模板。6. 三个算法的共同主线把KMP、Manacher、bfprt放一起讲完再回头看它们的联系。KMP的next数组是利用已匹配部分的公共前后缀信息避免主串回退Manacher的P数组是利用回文的镜像对称性避免重复扩展bfprt是分组取中位数再取中位数的中位数避免partition选到极端pivot。三个算法从不同的角度验证了同一个道理算法优化的本质是信息的最大化复用以及最坏情况的主动规避。这个道理应用到实际开发中很多性能问题都能找到优化思路。比如处理字符串时如果发现某些子串被反复计算就要考虑预处理记忆化处理大数据时如果某种选主元策略在极端输入下会退化就要考虑更稳妥的确定性策略。下一篇会展开bfprt的完整实现包括每组排序代码、中位数数组的递归处理、partition的三路划分以及几个变种题目第K大、找中位数、找出所有TopK元素的解法。到时候拿到代码建议先自己跑一遍再试着改一改比单纯看一遍印象深得多。我自己带过的学员里很多人卡在这三个算法上是因为眼高手低——看讲解都觉得懂了一写代码就各种边界问题。所以这里多说一句算法这东西看一百遍不如手写五遍写完再对着测试用例跑尤其要把刚才说的边界情况全部测一遍。这个过程不是浪费时间而是真正把别人的解法变成自己的内功。