ARTICLE DETAIL

资讯详情

深耕网站建设与运营推广的一线实战洞察。

分治与归并排序:核心思想、代码实现与高阶应用

分治与归并排序:核心思想、代码实现与高阶应用 1. 分治思想的核心把难题拆到能直接“上手”为止分治Divide and Conquer和归并Merge这对组合几乎是每个刷算法题的人绕不开的第一道坎。算法篇都写到第十篇了为什么专门把分治-归并单独拎出来讲因为这两者不只是某一道题、某一个排序算法的知识点它们代表了一整套解决问题的思维方式遇到一个大问题先把它拆成若干个规模更小、结构相同的小问题逐个解决之后再把这些小问题的解合起来拼出原问题的答案。这个思路听起来像“废话”但真正能在代码里把“拆、治、合”三个字落到位的人其实不多。很多人背熟了归并排序的模板可真换个题目比如“用分治法求一个n元素数组中最大元素的位置”就不知道从哪里下手了。这正是本篇文章想解决的事不只是让你记住归并排序怎么写而是让你彻底理解分治的骨架能在不同场景下自己搭出递归结构。这篇内容适合什么基础的人看我觉得只要是正在学算法、刷LeetCode或者备战面试的人都可以认真过一遍。零基础也能看因为我不会只给结论会把每一步的“为什么”也拆开讲。有基础的人也别急着走后面关于逆序对计数、CDQ分治、四边形不等式优化DP中的分治解法这些内容很多教科书是不展开讲的里面有不少我实战中积累的坑和经验值。先说一个最重要的认知分治不是一种具体的算法它是一种解决问题的宏观策略。归并排序、快速排序、二分搜索、大整数乘法、最近点对这些经典算法全是分治策略的具体表现形式。理解到这个层面“分治-归并”就从一个记忆性的知识点变成了一套可以迁移的思维工具。1.1 分治的三步走分解、解决、合并任何分治算法无论包装得多复杂核心骨架永远是这三步分解Divide把原问题拆成若干个子问题这些子问题形式上和原问题一样只是规模变小了。比如归并排序里把数组从中间一刀切成两半。解决Conquer递归地解决这些子问题。如果子问题已经小到可以直接算出答案那就直接算这就是所谓的“递归边界”。合并Combine把子问题的解组合成原问题的解。这一步往往是最容易出bug的地方也是区分“会背模板”和“真懂分治”的分水岭。我用一个生活化的类比来说明。假设你要统计公司全年12个月的销售总额但你一个人根本看不过来这么多数据。你会怎么做很自然地把12个月的数据分成上半年和下半年然后让两个小组分别统计6个月的数据最后把两个小组的统计结果相加。这就是一次典型的分治拆成两份各自算再合并。这个例子虽然简单但它揭示了分治能降低问题难度的关键所在处理12个月的数据比处理6个月的数据复杂不止两倍而分治把这个“复杂度曲线”拉平了。在算法层面这意味着把指数级或平方级的复杂度降成对数级或线性对数级。1.2 分治、递归、减治别再把它们混为一谈很多文章把分治和递归画等号这是不对的。递归是函数的自我调用机制是一种手段分治是一种策略。分治必然用递归来实现但递归不一定是分治。比如深度优先搜索DFS也是递归但DFS没有“把问题拆成独立子问题再合并”这个过程它是沿着一条路走到黑再回溯。所以DFS属于基于递归的搜索不属于分治。还有一个容易混淆的兄弟概念叫“减治”Decrease and Conquer。减治和分治的区别在于分治会拆成多个子问题分别处理后合并而减治只把问题规模减小一份然后只处理减小后的那份不需要合并或者只需要极轻量的合并。二分查找就是典型的减治每次砍掉一半只在一半里继续找根本没有“合并”的动作。搞清楚这个区别你就不会在写分治代码时莫名想尝试做不必要的合并步骤。分治最核心的使用前提有三个缺任何一个分治就可能不适用子问题与原问题结构相同否则无法递归。子问题之间互相独立如果子问题之间有重叠那应该用动态规划而不是分治。注意这里说的重叠和“合并时跨子问题的关系”不是一回事前者是子问题内部的计算被重复后者是原问题本身就需要结合子问题结果。合并操作的复杂度要可控如果合并需要遍历全量数据且无法优化那分治的收益可能被合并成本抵消。这三个前提决定了你拿到一道题能不能往分治上想。接下来我就用归并排序这个最经典的分治应用把这三步走落实到代码层面。2. 归并排序分治思想最经典的入门课归并排序Merge Sort是所有教科书讲到分治时都会先拿出来讲的例子原因很简单它把分治的三步走得非常清晰没有任何弯弯绕绕。你不需要理解复杂的递归调用时机只需要机械地“切两半、排两边、合起来”就能得到一个复杂度为O(n log n)的稳定排序算法。当你真正把归并排序的代码写熟之后会惊喜地发现它的价值远不止“排序”本身。逆序对计数、链表排序、外部排序、CDQ分治全都是在归并排序的骨架上做了扩展。可以说归并排序是通往高阶算法的一座必经桥梁。2.1 拆解归并排序的完整执行过程先看归并排序的三步怎么落到具体操作上。假设有个数组[38, 27, 43, 3, 9, 82, 10]分解阶段每次取数组的中点把数组切成两半。[38, 27, 43, 3] [9, 82, 10]继续对每一半做同样的操作直到每个子数组只剩一个元素[38, 27] [43, 3] [9, 82] [10]再拆[38] [27] [43] [3] [9] [82] [10]到这里解决阶段完成。因为一个元素的数组天然有序不需要做任何处理。这个“一个元素天然有序”的小事实就是归并排序的递归边界。然后进入合并阶段。这一步才是真正的重头戏。比如合并两个已排序的子数组[38]和[27]做法是两个子数组各放一个指针从头开始比较把更小的元素依次放入临时数组。比较 38 和 2727 小放入临时数组右指针右移。剩下 38直接放入临时数组。得到[27, 38]。用同样的方式合并[43]和[3]得到[3, 43]。再把[27, 38]和[3, 43]合并比较 27 和 33 小放入临时数组。比较 27 和 4327 小放入临时数组。比较 38 和 4338 小放入临时数组。放入剩下的 43。得到[3, 27, 38, 43]。右半边同理最后把两个大有序数组合并成完整有序数组。整个过程像两副按顺序排好的扑克牌每次从两副牌的顶牌里挑一张更小的放到手里直到全部挑完。这就是“分而治之”的全貌。你仔细感受一下合并两个有序数组的过程是O(n)的递归深度是O(log n)的所以总复杂度是O(n log n)。不需要复杂的数学推导直觉就能感受到这个效率的来源——每一层的合并总代价都是O(n)一共log n层总价就是O(n log n)。2.2 C实现归并排序的完整代码直接看代码。我用C写了一个类模板风格的版本方便复用#include iostream #include vector using namespace std; void merge(vectorint arr, int left, int mid, int right) { // 创建临时数组存放合并结果 vectorint temp(right - left 1); int i left; // 左半部分起始指针 int j mid 1; // 右半部分起始指针 int k 0; // 临时数组指针 // 双指针合并谁小谁先进临时数组 while (i mid j right) { // 注意这里用的是 保证相等元素的相对顺序不变 if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } // 如果左半段还有剩余全部拷贝进去 while (i mid) { temp[k] arr[i]; } // 如果右半段还有剩余全部拷贝进去 while (j right) { temp[k] arr[j]; } // 将临时数组拷贝回原数组对应位置 for (int p 0; p temp.size(); p) { arr[left p] temp[p]; } } void mergeSort(vectorint arr, int left, int right) { if (left right) return; // 递归边界只有一个元素或区间不合法 int mid left (right - left) / 2; // 防止溢出 mergeSort(arr, left, mid); // 递归排序左半 mergeSort(arr, mid 1, right); // 递归排序右半 merge(arr, left, mid, right); // 合并两个有序区间 } int main() { vectorint arr {38, 27, 43, 3, 9, 82, 10}; mergeSort(arr, 0, arr.size() - 1); for (int x : arr) cout x ; return 0; }有几个细节我必须单独拎出来讲因为新手经常在这上面翻车。第一递归边界是left right而不是left right。在某些情况下比如空数组或者参数传入时left已经大于right用可以多一层保护避免进入死递归。这种写法虽然看起来只是顺手多打了一个等号但在工程上能减少很多无谓的边界判断。第二计算中点用left (right - left) / 2不要用(left right) / 2。后者在left和right极大时可能整型溢出这在面试里是一个常被追问的细节。虽然普通测试数据不会触发但写成防溢出的形式是一个好习惯。第三合并时比较用而不是。这一点关乎排序的稳定性。如果左右两个元素相等先用左半数组的元素那么相等元素的相对顺序在排序前后保持不变归并排序因此成为稳定排序。如果写成相同值的元素会被右半数组的抢先移动稳定性就丢失了。我给一段合并时最关键的调试建议如果你想肉眼验证合并过程是否正确可以在每次merge之后打印一遍arr[left..right]。如果出现局部有序但合并后区间内出现乱序那问题几乎必然出在临时数组的拷贝范围上。我见过很多次“合并完前半段后半段被覆盖丢失”的情况就是因为for循环里写成了arr[p] temp[p]忘了加left偏置。2.3 复杂度、稳定性与适用场景分析归并排序是教科书里时间复杂度最稳定的排序算法之一最好、最坏、平均情况下都是O(n log n)。这和快排不同——快排最坏会退化到O(n^2)。归并的空间复杂度是O(n)因为每一层合并都需要一个临时数组但注意在实际实现里临时数组可以在每一层重新分配也可以全局只开一个长度为n的数组重复使用。后者对性能更友好能在一定程度上减少内存分配带来的开销。下表是几种常见排序算法的核心属性对比算法平均时间复杂度最坏时间复杂度空间复杂度稳定性归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n^2)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定从工程实际来看语言内置的排序算法比如C的std::sort并不是纯快排而是混合排序introsort数据量大时用快排递归深度过深时切换堆排序区间小于某阈值时用插入排序。归并排序虽然不如快排“快”但它的稳定性和对链表、外部排序的天然友好性决定了它在很多场景下无法被替代。比如链表排序如果要求O(n log n)且稳定归并排序是首选因为链表不支持随机访问快排的partition操作在链表上施展不开。理解了归并排序的代码和复杂度你已经掌握了分治的第一个经典应用。但分治的最大魅力在于同一个骨架换一个合并逻辑就能解决完全不同的问题。接下来我借热搜词里的“分治法求一个n元素数组中最大元素的位置”这道题展示怎么把分治的框架套到一个新问题上。3. 分治法求n元素数组最大元素的位置模板之外的思考方式搜索热词里有一道非常典型的题目“第1关分治法求一个n元素数组中最大元素的位置”。不少刷题平台把它作为分治思想的入门练习。这道题解法上并不复杂但它是一个很好的“思维试金石”你到底是背住了归并排序的代码还是真的理解了分治结构。如果你只记住了归并排序的固定写法拿到这道题可能会懵因为这里没有“排序”没有“合并有序数组”这些熟悉的影子。但其实你只要抓住“拆、解、合”这三个字思路会非常自然地流出来。先明确题目要求给定一个数组a[0..n-1]返回最大元素的下标。如果最大元素出现多次通常要求返回第一个或者任意一个看题目规则。朴素解法人人都能写从0到n-1遍历一遍记录当前最大值和下标遇到更大的就更新。时间复杂度O(n)非常简单且高效。那为什么还要用分治直接回答这道题用分治并不比线性扫描更快但它是练习分治架构的一个好载体。分治的价值不在于击败朴素解而在于让你建立“如何把大问题拆成小问题、再把解合并”的肌肉记忆为后面遇到真正有意义的分治问题打基础。3.1 拆解思路最大值的位置是如何“合并”出来的分治思路如下分解把数组从中间mid切成两半左半[left, mid]右半[mid1, right]。解决递归地在左半找最大元素的位置posL递归地在右半找最大元素的位置posR。递归边界就是区间里只有一个元素那位置就是left本身。合并比较a[posL]和a[posR]。如果a[posL] a[posR]返回posL否则返回posR。这就是合并规则。关键点来了合并规则的本质就是“比较胜负”。你把找最大值的问题拆成了两个半区间的“局部冠军”然后让两个局部冠军打一架胜者就是整个区间的冠军。如果题目要求返回第一个出现的位置那么a[posL] a[posR]时选左用如果要求返回任意位置用也无所谓。我故意把“第一个出现位置”这个要求单独说因为很多人在合并规则的比较符号上栽过跟头。比如数组[5, 3, 5]最大元素是5第一个出现位置是0。如果你在合并时用而不是那么当左半和右半的冠军值相等时你会选右半的冠军返回的位置就是2这和题目要求冲突。这是一个非常隐蔽的小细节一不留神就出错。3.2 C实现与测试用例直接上代码#include iostream #include vector #include climits using namespace std; // 返回 [left, right] 区间内最大元素的索引若最大值重复返回最靠左的 int findMaxPos(const vectorint arr, int left, int right) { if (left right) { return left; // 递归边界单个元素就是区间最大值 } int mid left (right - left) / 2; int posL findMaxPos(arr, left, mid); // 左半区间冠军 int posR findMaxPos(arr, mid 1, right); // 右半区间冠军 // 合并规则相等时优先选择左半区间保证第一个最大值 if (arr[posL] arr[posR]) { return posL; } else { return posR; } } int main() { vectorint arr {5, 3, 5, 2, 8, 1, 8, 7}; int pos findMaxPos(arr, 0, arr.size() - 1); cout 最大元素: arr[pos] 位置: pos endl; return 0; }对这个测试数组运行结果应该是最大元素8位置40-based索引。因为虽然8在位置6也出现了一次但合并规则用保证了返回的是靠左的第一个。你可能会问这个递归的复杂度是多少每次把区间一分为二每个元素在每一层最多被比较一次递归深度为log n所以总比较次数是O(n)的量级准确说法是每个元素每层都会参与比较总比较次数为n-1次可以画递归树验证。和线性扫描的n-1次比较完全一致。所以这个分治解法在线性视角下并没有比朴素解法“更快”它只是把比较的顺序从“一趟遍历”变成了“两两对战淘汰赛”。从工程角度这个解法“浪费”了递归栈的空间但作为面试题面试官考察的不是你的性能而是你是否拥有“拆分子问题然后合并”的思维。我在实际参与面试时遇到候选人能很快写出朴素解法但只有真正理解了分治的人才能在提示“试试分治”后用几分钟时间把这段递归写对。这道题就像学骑车时用的辅助轮它不用于长途骑行但能帮你找到平衡感。4. 从归并走向高阶逆序对、CDQ分治与DP优化如果说上一节的找最大值是分治的“辅助轮”那么这一节的内容就是真正的“公路骑行”。归并排序的合并过程里藏着一个极其有价值的副产品逆序对计数。而逆序对计数再往上扩展一步就进入了CDQ分治的领域——一种在算法竞赛和高端面试中被反复考察的分治思想。另外热搜词里还出现了“四边形不等式优化dp 分治解法 二分解法”这属于分治在动态规划领域的精妙应用。我会把这三个方向逐个拆开讲透。4.1 利用归并排序计算逆序对什么是逆序对对于一个数组如果i j但a[i] a[j]那么(i, j)就是一个逆序对。逆序对的数量反映了一个数组的“混乱程度”。比如[2, 3, 1]中逆序对有(2,1)和(3,1)两个所以逆序对数量是2。朴素解法是双重循环O(n^2)复杂度。数据量一大比如10^5以上就会超时。而归并排序可以在O(n log n)时间内求解逆序对具体做法是在合并两个有序子数组的过程中如果右半数组的某个元素比左半数组当前元素小那么这个“更小”的元素会与左半数组剩余的所有元素形成逆序对。听起来有点绕我逐步说。假设合并时左半数组是[4, 5, 6]右半数组是[1, 2, 3]。双指针从头开始右指针的值是1左指针的值是41 4说明1应该排在4前面。那么对于1来说它在原数组中的位置在右半区而4、5、6三个数都在左半区且左半区的索引都小于右半区的索引。因此(4,1)、(5,1)、(6,1)构成三个逆序对。此时只需要把左半数组剩余长度mid - i 1累加到答案中即可而不需要逐一比较。然后左指针移动继续合并。一句口诀归并合并阶段右半元素小于左半当前元素时逆序对数量增加“左半剩余元素个数”。代码实现long long mergeCount(vectorint arr, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, k 0; long long cnt 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { // arr[j] 比 arr[i] 小则 arr[i..mid] 所有元素都与 arr[j] 构成逆序对 cnt (mid - i 1); temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int p 0; p temp.size(); p) { arr[left p] temp[p]; } return cnt; } long long mergeSortCount(vectorint arr, int left, int right) { if (left right) return 0; int mid left (right - left) / 2; long long cnt 0; cnt mergeSortCount(arr, left, mid); cnt mergeSortCount(arr, mid 1, right); cnt mergeCount(arr, left, mid, right); return cnt; }注意这里的累加变量类型建议用long long。逆序对数量在极端情况下数组完全逆序可以达到n*(n-1)/2对于n10^5就是约50亿超过int范围。这种细节在竞赛里很常见丢了分都不知道丢在哪。逆序对计数常被包装成各种题目求“重要逆序对”右半元素比左半元素的两倍还小、求“翻转对”等。变体虽然多核心都是在合并阶段多写一个统计条件。能亲手把逆序对计数写对你对归并排序的掌握就比大多数人扎实了。4.2 CDQ分治归并排序思想的高级形态如果你对算法竞赛有过接触应该听说过CDQ分治的大名。它本质上就是归并排序思想的进一步升华。让我用一种尽量易懂的方式来解释它到底是什么。想象你有一组“事件”每个事件包含多个维度比如时间、位置、数值。你想统计在这些事件中满足某种“偏序关系”的事件对有多少。一个常见场景是二维偏序平面上有n个点对于每个点统计它左下方向有多少个点横纵坐标都小于等于它的点。CDQ分治的处理方法是按第一维比如x坐标排序。排序后第一维的偏序关系就被“拍平”了。此时问题变成在已经按x排序的序列中统计每个元素前面有多少个元素的y坐标小于等于它的y坐标。这不就是一个经过变形的“逆序对”问题吗分治处理递归处理左半区间和右半区间。关键在合并时左半区间的所有元素x坐标都小于右半区间的元素因为按x排过序那么左半对右半的贡献只需要看y坐标的大小关系。这时候就可以双指针扫描把“符合某个y坐标条件”的左半元素数量累加到右半元素答案中。左右区间内部的贡献通过递归求解跨区间的贡献通过合并阶段求解。每个元素不会重复计数也不会被漏掉。这个模式与归并排序的关联一目了然分治拆区间、合并阶段处理跨区间的逻辑左右有序保证合并阶段可以用双指针线性完成。只是归并排序合并阶段做的事情是“按大小合并”CDQ分治合并阶段做的是“统计偏序关系”。同一个骨架换一个合并逻辑解决完全不同的问题。如果你是靠理解而不是死记来掌握归并排序的你会发现CDQ分治学起来特别顺畅。CDQ分治还能扩展到三维偏序也就是“陌上花开”那道经典题。做法是第一维排序第二维用CDQ第三维在CDQ合并时用树状数组维护前缀数量。难度再上一个台阶但思路的源头仍然在这里。4.3 四边形不等式优化DP中的分治解法与二分解法热搜词里有一句“四边形不等式优化dp 分治解法 二分解法”这个知识点看起来很高深但它的核心逻辑其实也是一个分治架构。很多DP递推式长这样dp[i][j] min_{k in [j-1, i-1]} (dp[k][j-1] cost[k1][i])直接枚举k的时间复杂度是O(n^3)但在某些cost函数满足“四边形不等式”的条件下最优决策点opt[i][j]关于i具有单调性也就是随着i增大最优的k也只会增大不会回退。这个性质叫“决策单调性”。有了它就可以用分治来优化。分治解法是这样的设当前要计算的dp区间是[l, r]已知这段区间内所有状态的最优决策点的候选范围是[optL, optR]。取中点mid (l r) / 2暴力枚举k在[optL, min(mid-1, optR)]范围内所有可能的转移找出dp[mid][j]的最优决策点bestK。记录答案。因为决策单调性[l, mid-1]的决策点范围被约束到[optL, bestK][mid1, r]的决策点范围被约束到[bestK, optR]。递归计算左右两半。每一层枚举的决策点总数是O(n)递归深度是O(log n)总复杂度O(n log n)。写成代码它就是一套标准的分治结构只是“分解”的对象从数组变成了决策区间“合并”的动作变成了“用找到的最优决策点去划分下一层的候选范围”。那“二分解法”又是什么它本质上是决策单调性在“同一层不互相依赖”前提下的另一种利用方式。从另一个角度看决策单调性意味着opt[i]数组在某个维度上单调递增。二分法就是利用这个单调性对每个位置通过二分找到它“作为最优决策点”影响的状态区间然后用一个数据结构去更新这些区间。分治解法的优势是写起来直观、不容易错二分解法在某些情况下常数更小、且可以配合维护全局最优值的结构来使用。两者思路同源但代码形态差别很大。对一个普通的算法工程师来说面试中让你写四边形不等式优化DP的概率不高但从分治视角理解“决策区间被递归分解”的过程能极大地提高你对分治概念的敏感度。以后遇到任何题目只要看出决策点具有单调性脑子里就会立刻蹦出分治这个选项而在优化DP的领域分治和解法两种手段并列选择的关键是看状态依赖方向如果每层状态只依赖上一层分治法通常更省心。5. 从零写分治代码时最常踩的坑分治的框架看起来只有三行但真正动手写的时候几乎每个人都会踩到类似的坑。我把这些年反复遇到的典型问题整理成一个速查表每一条都用“现象-原因-解法”来说明希望能帮你省下大量调试时间。常见问题具体现象根本原因解决方案递归栈溢出程序运行到一半直接崩溃递归边界条件错误导致无限递归检查left right边界尤其是空数组和单元素数组合并区间错乱排序后部分元素丢失或重复临时数组拷贝回原数组时没有正确偏移拷贝循环中使用arr[left p] temp[p]中点计算溢出大数组排序结果完全错误使用(left right) / 2导致int溢出改用left (right - left) / 2稳定性丢失相同元素排序后相对顺序变了合并时用而不是合并比较改为arr[i] arr[j]栈空间反复分配导致效率低数据量大时运行明显变慢每次merge都动态分配临时vector在mergeSort外层一次性申请临时数组merge时复用除了表格里的硬错误还有两个软问题也值得单独说。第一个是递归出口的语义。很多新手以为“最大元素的位置”这个问题递归边界应该返回arr[left]值而不是left下标。如果返回值你在合并时比较的还只是值但最终需要输出位置时就拿不到下标了。所以递归边界的返回值类型必须和最终需求保持一致要求位置就返回位置。第二个是理解“合并”发生在递归回溯时。分治代码的执行顺序是先一路递归到最深处再从底层开始逐层向上合并。如果你想打印归并排序每一层的中间结果应该在merge函数的开头打印left, mid, right而不是在mergeSort刚进入时打印。这一点常常让调试者困惑为什么打印的顺序不是从上到下而是从下到上原因就是递归先深入再回溯合并动作发生在回溯阶段。我个人调试分治代码的习惯是先构造一个包含重复元素、负数和偶数个元素的数组跑一遍看看是否符合预期再构造函数式随机数据做对拍用小规模遍历结果验证。对拍这个手段在任何一个稍微复杂的算法题目里都极其有用。你不需要一次性把代码写对只需要能快速找出错误位置其余交给“机器验证”。6. 写在最后的经验分享分治思想的长远价值不仅在于算法题本身。即使你日后不做算法竞赛、不面试大厂工作中遇到数据处理、日志聚合、大规模统计这些问题时“分治”的思路依然适用——把大任务拆成小任务分配给不同线程或机器处理最后再汇总结果。MapReduce的核心思想就是分治分布式系统里的“两阶段提交”、搜索引擎里的排序合并到处都有它的影子。我在带新人时经常说一句话分治算法是最容易“背会”也最容易“背废”的知识点。背会了你能写出归并排序背废了你换一道题就不会做。真正值钱的理解是遇到一个陌生问题能敏锐识别出“这里能不能分治”“合并逻辑应该做什么”。要做到这一点没有捷径只能靠多动手写、多对比变体题来积累。最后分享一个小技巧拿到一道陌生题先别急着写代码拿笔在纸上画一棵递归树把“分解到什么程度停”“合并在做什么事”写清楚。这一步花不了五分钟但能避免九成以上的“思路混乱”。分治的骨架一旦搭好剩下的就是往里面填细节。这条路看起来慢实际是最快的。
返回列表