經(jīng)常有人問我分治和歸并到底是兩個(gè)東西還是一個(gè)東西。我的回答是它們是一對(duì)黃金搭檔。分治是方法論解決問題時(shí)把大任務(wù)拆成小任務(wù)再把小任務(wù)的結(jié)果匯總成大結(jié)果歸并是這場拆解之后最經(jīng)典的合并動(dòng)作把兩個(gè)有序序列合成一個(gè)有序序列。如果你正在學(xué)算法或者刷題時(shí)被一堆“遞歸爆?！薄爸羔樤浇纭闭勰ミ@篇文章就是寫給你看的。我會(huì)從分治的底層邏輯講起接著把歸并排序的代碼徹底拆透再順手解決幾個(gè)高頻經(jīng)典問題最后分享一些進(jìn)階玩法和踩坑實(shí)錄。所有代碼用C寫牽扯到復(fù)雜度推導(dǎo)的地方我會(huì)算給你看。文章不會(huì)太長篇大論講廢話該給代碼給代碼該給經(jīng)驗(yàn)給經(jīng)驗(yàn)。1. 分治思想的底層邏輯不是簡單的“拆了再合”1.1 分治的核心三件套分治思想聽起來玄乎本質(zhì)上就三步分解、解決、合并。把原來規(guī)模為 n 的問題拆成若干個(gè)規(guī)模更小的同類子問題子問題繼續(xù)遞歸拆直到小到可以直接解決然后逐層返回把子問題的解合并成原問題的解。我習(xí)慣用一個(gè)生活例子來解釋。假設(shè)你要在一堆撲克牌里找出最大的那一張正常思路是拿著一張一張比O(n) 次比較就結(jié)束了。分治的思路是把這堆牌從中間分成兩堆分別找出兩堆各自的最大牌再比較這兩張誰更大。你可能會(huì)覺得這不是多此一舉嗎但注意當(dāng)“找出最大值”升級(jí)成“給整副牌排序”或者“統(tǒng)計(jì)多少對(duì)元素是逆序的”單次遍歷解決不了分治的價(jià)值就體現(xiàn)出來了。分治真正厲害的地方不在“拆”而在“合”。很多新手只把分治理解成遞歸 折半然后寫出來的代碼只是形式上的分治合并階段沒有任何信息利用那自然快不起來。歸并排序的合并階段利用了“兩個(gè)子數(shù)組已經(jīng)有序”這個(gè)已知條件才能在 O(n) 時(shí)間內(nèi)把兩個(gè) n/2 規(guī)模的子數(shù)組合并成有序數(shù)組從而把整體復(fù)雜度做到 O(n log n)。1.2 為什么分治能跑得比暴力快這里不得不做一點(diǎn)簡單的復(fù)雜度推導(dǎo)。以歸并排序?yàn)槔O(shè) T(n) 是排序 n 個(gè)元素所需時(shí)間遞歸地看T(n) 2T(n/2) O(n)意思是排序 n 個(gè)元素分解成兩個(gè) n/2 規(guī)模的子問題各花 T(n/2)合并兩個(gè)有序數(shù)組要花 O(n)。展開這個(gè)遞推式每一層總的比較工作量都是 O(n)遞歸深度一共 log2(n) 層所以 T(n) O(n log n)。對(duì)比冒泡排序和插入排序的 O(n2)n 從 10 萬到 100 萬規(guī)模時(shí)O(n log n) 和 O(n2) 的差距不是一倍兩倍而是千倍萬倍。你想想如果核心業(yè)務(wù)接口里有一段 O(n2) 的排序邏輯數(shù)據(jù)一漲接口就超時(shí)換成歸并或快排瓶頸往往立刻消失。主定理把這些規(guī)律總結(jié)成了公式。形如 T(n) aT(n/b) O(n^d) 的遞推式滿足條件時(shí)復(fù)雜度可以直接查表得出。分治算法的場景非常多歸并排序、快速排序、最近點(diǎn)對(duì)、快速冪、歸并求逆序?qū)诵亩际沁@套“分解-解決-合并”的思路。我踩過的一個(gè)坑是分治的子問題必須互相獨(dú)立合并代價(jià)必須可控。如果子問題之間有大量重疊強(qiáng)行分治只會(huì)浪費(fèi)遞歸開銷這時(shí)候應(yīng)該用動(dòng)態(tài)規(guī)劃或記憶化搜索。反過來如果合并操作本身就需要 O(n2)那整體復(fù)雜度還會(huì)被合并拖累分治的收益也會(huì)被抵消。2. 歸并排序最標(biāo)準(zhǔn)的分治實(shí)戰(zhàn)2.1 核心代碼逐行拆解歸并排序是分治思想最樸素的實(shí)現(xiàn)。我先把完整代碼貼出來再逐段講為什么這樣寫。#include bits/stdc.h using namespace std; void merge(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; // 左半部分起點(diǎn) int j mid 1; // 右半部分起點(diǎn) int k left; // 臨時(shí)數(shù)組寫入位置 // 雙指針掃描誰小誰先進(jìn)臨時(shí)數(shù)組 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]; } // 把合并結(jié)果復(fù)制回原數(shù)組 for (int idx left; idx right; idx) { arr[idx] temp[idx]; } } void mergeSort(vectorint arr, int left, int right, vectorint temp) { if (left right) { return; // 單個(gè)元素已經(jīng)有序 } int mid left ((right - left) 1); // 防溢出寫法 mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); }遞歸的邊界是left right。當(dāng)區(qū)間里只有一個(gè)元素或沒有元素時(shí)它天然有序不需要繼續(xù)拆。mid的計(jì)算我特意用了left ((right - left) 1)而不是(left right) 1主要防止 left 和 right 都很大時(shí)整數(shù)溢出。雖然刷題時(shí)數(shù)據(jù)范圍可能到不了那個(gè)量級(jí)但好習(xí)慣要養(yǎng)起來。合并函數(shù)的核心是兩個(gè)指針 i 和 j分別指向左右兩個(gè)子數(shù)組的當(dāng)前元素。誰小就先把誰放進(jìn)臨時(shí)數(shù)組然后對(duì)應(yīng)指針往后走。這個(gè)“雙指針歸并”的手法值得背下來后面求逆序?qū)Α⑶笮『蛦栴}全都還會(huì)用到它。2.2 穩(wěn)定性與空間占用歸并排序是穩(wěn)定的排序算法這一點(diǎn)和快速排序不一樣。代碼里我用的是if (arr[i] arr[j])當(dāng)左右兩個(gè)元素相等時(shí)優(yōu)先取左半邊的元素放進(jìn)臨時(shí)數(shù)組。因?yàn)樽蟀脒叺脑卦谠瓟?shù)組中本來就出現(xiàn)在右半邊之前這樣做保證了相等元素的相對(duì)順序不變?？臻g占用方面合并時(shí)需要一塊長度等于當(dāng)前區(qū)間的臨時(shí)數(shù)組。我是在函數(shù)外預(yù)先分配好一整塊temp長度和原數(shù)組一樣每次合并都復(fù)用這塊空間。這樣做的原因是如果每次遞歸都在函數(shù)內(nèi)部新建臨時(shí)數(shù)組總的空間開銷會(huì)變成 O(n log n)而且頻繁分配內(nèi)存帶來的常數(shù)時(shí)間非?？捎^。實(shí)測下來大數(shù)據(jù)量下每次分配臨時(shí)數(shù)組的版本可能慢上三四倍。時(shí)間上歸并排序的 O(n log n) 是穩(wěn)定可預(yù)期的不依賴輸入數(shù)據(jù)的初始狀態(tài)。這一點(diǎn)比快排更讓人安心快排在極端情況下會(huì)退化到 O(n2)而歸并永遠(yuǎn)不會(huì)。2.3 歸并排序的應(yīng)用邊界歸并排序有一個(gè)優(yōu)勢場景常常被忽略鏈表排序。數(shù)組版的歸并需要額外臨時(shí)數(shù)組但鏈表版的歸并不需要額外空間只要改指針就能完成合并空間復(fù)雜度直接降到 O(1)。LeetCode 上一堆鏈表排序題用歸并幾乎是常規(guī)解法。數(shù)組場景里如果數(shù)據(jù)量不大、對(duì)穩(wěn)定性沒有特殊要求大多數(shù)時(shí)候直接用內(nèi)置 sort快排 插入排序混合就夠了常數(shù)小、代碼簡單。但一旦遇到“不僅排序還需要在排序過程中統(tǒng)計(jì)信息”的問題比如逆序?qū)Α⑿『蛦栴}歸并排序就是唯一能同時(shí)完成排序和統(tǒng)計(jì)的選擇。這類問題我在下一節(jié)詳細(xì)展開。3. 分治經(jīng)典問題進(jìn)階從排序到統(tǒng)計(jì)3.1 分治法求最大元素位置先看一個(gè)很多人刷題時(shí)遇到的第一關(guān)分治法求一個(gè) n 元素?cái)?shù)組中最大元素的位置。很多在線實(shí)驗(yàn)平臺(tái)把這道題放在“分治”第一關(guān)因?yàn)樗壿嫼唵?、結(jié)構(gòu)清晰。int getMaxIndex(vectorint arr, int left, int right) { if (left right) { return left; // 只剩一個(gè)元素它自己就是最大值 } int mid left ((right - left) 1); int leftMaxIdx getMaxIndex(arr, left, mid); int rightMaxIdx getMaxIndex(arr, mid 1, right); // 合并比較左右兩個(gè)最大值返回較大的下標(biāo) if (arr[leftMaxIdx] arr[rightMaxIdx]) { return leftMaxIdx; } return rightMaxIdx; }注意幾點(diǎn)。第一題目要求返回位置所以我返回的是下標(biāo)不是值。第二多個(gè)最大值同時(shí)存在時(shí)我用了保證返回的是“第一個(gè)”最大元素的位置這是很多題目隱含的細(xì)節(jié)要求。第三這個(gè)算法的時(shí)間復(fù)雜度是 O(n)因?yàn)槊恳粚雍喜⒅蛔鲆淮伪容^但遞歸壓棧的深度是 O(log n)也算順帶復(fù)習(xí)了遞歸。有一點(diǎn)我必須說清楚真正在工程環(huán)境中找最大值位置線性掃描就夠了幾行代碼搞定int maxPos 0; for (int i 1; i n; i) { if (arr[i] arr[maxPos]) maxPos i; }分治版的意義在于教學(xué)。它能幫你熟練“把大區(qū)間拆成兩個(gè)小子區(qū)間再合并子區(qū)間結(jié)果”的模式為后面更復(fù)雜的分治問題打基礎(chǔ)。別把精力浪費(fèi)在糾結(jié)“為什么不用遍歷”上把分治模板練熟才是正事。3.2 逆序?qū)τ?jì)數(shù)逆序?qū)Χx很簡單i j 時(shí)若 a[i] a[j]這倆元素構(gòu)成一個(gè)逆序?qū)?。暴力算法兩兩比較O(n2)數(shù)據(jù)量一上萬就卡死。歸并排序版的解法時(shí)間復(fù)雜度 O(n log n)原理非常巧妙。核心思想藏在合并階段。假設(shè)當(dāng)前需要合并左數(shù)組 [left, mid] 和右數(shù)組 [mid1, right]兩邊各自已經(jīng)有序。當(dāng)右數(shù)組的指針 j 指向的元素比左數(shù)組指針 i 指向的元素小時(shí)說明 a[i..mid] 里所有元素都大于 a[j]因?yàn)樽髷?shù)組是有序的a[i] 已經(jīng)是左邊區(qū)間里最小的那個(gè)所以 a[j] 和左數(shù)組剩余元素一一構(gòu)成逆序?qū)δ嫘驅(qū)?shù)量直接累加mid - i 1。long long mergeCount(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; int j mid 1; int k left; long long invCount 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { // arr[j] 與 a[i..mid] 所有元素都構(gòu)成逆序?qū)?invCount (mid - i 1); temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int idx left; idx right; idx) { arr[idx] temp[idx]; } return invCount; } long long mergeSortCount(vectorint arr, int left, int right, vectorint temp) { if (left right) { return 0; } int mid left ((right - left) 1); long long count 0; count mergeSortCount(arr, left, mid, temp); count mergeSortCount(arr, mid 1, right, temp); count mergeCount(arr, left, mid, right, temp); return count; }這里有一個(gè)特別容易踩的坑逆序?qū)?shù)量要開long long不能開int。一個(gè)長度為 100000 的數(shù)組如果完全逆序排列逆序?qū)?shù)量是 n(n-1)/2大約 5 × 10^9早就超出 int 的最大值 2.1 × 10^9 了。我之前因?yàn)橥祽杏?int 交題WA 了一次才反應(yīng)過來白白浪費(fèi)十幾分鐘調(diào)試時(shí)間。3.3 小和問題小和問題和逆序?qū)κ峭惶啄０宓膬蓚€(gè)變體。定義是數(shù)組中每個(gè)元素左邊所有比它小的元素值之和累加所有元素就是小和。舉個(gè)例子數(shù)組 [1, 3, 5, 2, 4]3 左邊比它小的有 1貢獻(xiàn) 15 左邊比它小的有 1 和 3貢獻(xiàn) 42 左邊比它小的有 1貢獻(xiàn) 14 左邊比它小的有 1、3、2貢獻(xiàn) 6總和是 12。暴力解是 O(n2)。歸并解法的視角是反過來的與其統(tǒng)計(jì)每個(gè)元素左邊有哪些更小值不如統(tǒng)計(jì)每個(gè)值作為“更小值”時(shí)被多少個(gè)右側(cè)元素借用。合并時(shí)如果左數(shù)組當(dāng)前元素 a[i] 小于等于右數(shù)組當(dāng)前元素 a[j]說明 a[i] 比右數(shù)組從 j 到 right 的所有元素都小貢獻(xiàn)就是a[i] * (right - j 1)。long long mergeSmallSum(vectorint arr, int left, int mid, int right, vectorint temp) { int i left; int j mid 1; int k left; long long sum 0; while (i mid j right) { if (arr[i] arr[j]) { // arr[i] 小于右數(shù)組剩余元素累加貢獻(xiàn) sum (long long)arr[i] * (right - j 1); 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 idx left; idx right; idx) { arr[idx] temp[idx]; } return sum; }乘法運(yùn)算這里同樣要注意強(qiáng)制轉(zhuǎn)long long避免兩個(gè) int 相乘溢出。這類歸并統(tǒng)計(jì)問題只要吃透了逆序?qū)δ翘住袄糜行蛐耘坑?jì)算”的思路基本可以舉一反三。4. 歸并的進(jìn)階場景不止于排序4.1 多路歸并與外部排序歸并思想在最基礎(chǔ)的排序之外還有兩個(gè)經(jīng)典延伸場景多路歸并和外部排序。先看多路歸并。當(dāng)你有 k 個(gè)已經(jīng)有序的序列想合并成一個(gè)有序序列兩兩歸并需要做 k-1 次歸并。每次歸并比較兩個(gè)序列的頭部元素復(fù)雜度可以接受但當(dāng)序列數(shù)量很多時(shí)每輪尋找 k 個(gè)頭部中的最小值需要 k-1 次比較整體效率會(huì)下降。工程上的做法是用一個(gè)大小為 k 的堆來維護(hù) k 個(gè)序列的當(dāng)前頭部元素每次彈出最小值所在序列的頭部然后從該序列補(bǔ)充下一個(gè)元素進(jìn)堆。這樣每次取最小值的代價(jià)從 O(k) 降到 O(log k)。更進(jìn)一步的數(shù)據(jù)結(jié)構(gòu)是敗者樹專門為多路歸并設(shè)計(jì)在磁盤外部排序的場景里已經(jīng)用了很多年。外部排序處理的是“內(nèi)存裝不下”的數(shù)據(jù)。假設(shè)內(nèi)存只能放下 100MB但待排序文件有 10GB。思路是把大文件切成若干小塊每塊在內(nèi)存內(nèi)排好序?qū)懗龀膳R時(shí)文件最后用多路歸并把這些有序臨時(shí)文件邊讀邊合合并結(jié)果直接寫到最終輸出文件。歸并排序在這里不只是算法題了它直接決定了數(shù)據(jù)庫排序、日志排序這些基礎(chǔ)功能的性能。我在實(shí)際項(xiàng)目里做過 GB 級(jí)日志文件的排序當(dāng)時(shí)就是用了這個(gè)套路把內(nèi)排序和外歸并拆開處理穩(wěn)得很。4.2 四邊形不等式優(yōu)化DP分治解法與二分解法歸并能在排序過程中順帶統(tǒng)計(jì)信息已經(jīng)屬于進(jìn)階內(nèi)容但分治思想還能再往前走一步優(yōu)化動(dòng)態(tài)規(guī)劃。熱搜里那個(gè)“四邊形不等式優(yōu)化 dp 分治解法 二分解法”是最容易讓初學(xué)者懵圈的一類題。先交代背景。有些 DP 的狀態(tài)轉(zhuǎn)移形如 dp[i] min(dp[j] cost(j, i))暴力枚舉所有 j 是 O(n2)。如果 cost 函數(shù)滿足四邊形不等式那么 DP 的最優(yōu)決策點(diǎn)會(huì)隨 i 單調(diào)遞增也就是“決策單調(diào)性”。這個(gè)性質(zhì)一起就能用分治在 O(n log n) 內(nèi)求解。分治解法的核心是遞歸求解某個(gè)區(qū)間 [l, r] 的 dp 值時(shí)同時(shí)傳入一個(gè)可能的決策點(diǎn)搜索區(qū)間 [optL, optR]每次枚舉決策點(diǎn)時(shí)只在這個(gè)區(qū)間里找。算出中點(diǎn) mid 的最優(yōu)決策點(diǎn) optMid 后遞歸求解左半?yún)^(qū)間時(shí)搜索區(qū)間收縮為 [optL, optMid]遞歸求解右半?yún)^(qū)間時(shí)搜索區(qū)間收縮為 [optMid, optR]。因?yàn)闆Q策單調(diào)性保證了區(qū)間的收縮不會(huì)遺漏最優(yōu)解總的枚舉量被壓縮到 O(n log n)。二分解法的思路是另一條路。既然決策點(diǎn)隨 i 單調(diào)就可以逐個(gè)確定每個(gè)決策點(diǎn)“接管”的狀態(tài)區(qū)間。常見實(shí)現(xiàn)是維護(hù)一個(gè)單調(diào)棧或雙端隊(duì)列每個(gè)隊(duì)列元素保存“決策點(diǎn) 它作為最優(yōu)決策的狀態(tài)范圍”新決策點(diǎn)加入時(shí)用二分找到它接管范圍的邊界。整體復(fù)雜度同樣是 O(n log n)但編碼細(xì)節(jié)和分治解法差異很大。我個(gè)人的體會(huì)是如果比賽或面試中遇到這類題優(yōu)先考慮分治解法。原因很簡單分治解法的代碼模板和歸并排序的遞歸結(jié)構(gòu)相似思維負(fù)擔(dān)小邊界條件也更直觀。二分棧的寫法對(duì)邊界非常敏感我自己寫過幾次每逢“開區(qū)間閉區(qū)間”“最優(yōu)值相等時(shí)取哪個(gè)決策點(diǎn)”這些細(xì)節(jié)都會(huì)卡殼。你需要根據(jù)自己對(duì)哪種模板更熟悉來做選擇。5. 踩坑實(shí)錄分治代碼的邊界地獄5.1 遞歸邊界你寫對(duì)了嗎分治遞歸最常見的錯(cuò)誤就是邊界處理。mergeSort里我用的邊界是if (left right) return;這個(gè)寫法做了兩件事區(qū)間里有一個(gè)元素時(shí)返回區(qū)間為空時(shí)也返回。有的寫法寫if (left right)當(dāng)調(diào)用方不小心傳入空區(qū)間就會(huì)死循環(huán)或越界。建議一律寫?zhàn)B成習(xí)慣。合并循環(huán)里的邊界同樣要小心。while (i mid j right)的兩端邊界都取等號(hào)因?yàn)閮蓚€(gè)子數(shù)組的元素都要被掃描到不能漏掉最后一個(gè)?？截惢卦瓟?shù)組時(shí)循環(huán)也是for (int idx left; idx right; idx)從 left 到 right不是從 0 開始也不是到 n-1 結(jié)束。5.2 mid 計(jì)算的防溢出寫法mid left ((right - left) 1)這個(gè)寫法我是強(qiáng)烈推薦的。老寫法(left right) / 2在 left 和 right 都是 2^31 量級(jí)時(shí)可能溢出成負(fù)數(shù)結(jié)果完全錯(cuò)誤。雖然普通刷題數(shù)據(jù)一般不會(huì)觸發(fā)但工程代碼里數(shù)組索引完全可能很大一次溢出就是隱蔽的 bug調(diào)試成本極高。新寫法把減法優(yōu)先算了永遠(yuǎn)不會(huì)溢出。還有一個(gè)小細(xì)節(jié)右移一位需要加括號(hào)因?yàn)檫\(yùn)算符優(yōu)先級(jí)里右移低于加減法。寫成left (right - left) 1會(huì)變成(left right - left) 1實(shí)際等于right 1直接整段邏輯錯(cuò)亂。5.3 臨時(shí)數(shù)組的復(fù)用與性能我見過很多初學(xué)者喜歡在 merge 函數(shù)內(nèi)部寫vectorint temp(right - left 1);邏輯沒錯(cuò)但性能很差。每次合并都觸發(fā)一次內(nèi)存分配遞歸的每一層都會(huì)做很多次分配總分配次數(shù)是 O(n) 級(jí)別而內(nèi)存分配本身是個(gè)昂貴操作。正確的做法是在mergeSort外層初始化一整個(gè)temp長度等于原數(shù)組長度然后遞歸過程中所有區(qū)間合并共用這塊空間。因?yàn)楹喜⒉僮魇谴械耐粋€(gè)位置不會(huì)同時(shí)被兩個(gè)合并使用安全得很。實(shí)測對(duì) 100 萬元素的數(shù)組排序復(fù)用臨時(shí)數(shù)組的版本比每次新建的版本快一倍以上這個(gè)優(yōu)化是白賺的。5.4 相等元素順序與穩(wěn)定性歸并合并時(shí)if (arr[i] arr[j])決定了穩(wěn)定性。寫成會(huì)變成不穩(wěn)定排序雖然對(duì)純數(shù)值排序結(jié)果沒影響但如果你排序的是一個(gè)對(duì)象數(shù)組按某個(gè)字段排序穩(wěn)定性和不穩(wěn)定性的結(jié)果可能完全不同。舉個(gè)例子先按時(shí)間排序再按優(yōu)先級(jí)排序穩(wěn)定排序能讓相同優(yōu)先級(jí)的元素保留原時(shí)間順序不穩(wěn)定排序則可能打亂。我在實(shí)際開發(fā)中確實(shí)遇到過一次這個(gè)需求。按訂單創(chuàng)建時(shí)間排好序后需要再按用戶等級(jí)分組排序同時(shí)保留組內(nèi)的時(shí)間順序。如果手寫的歸并排序用的是分組后時(shí)間順序就亂了排查半天才發(fā)現(xiàn)是穩(wěn)定性寫錯(cuò)了。5.5 數(shù)據(jù)溢出的隱蔽炸彈歸并的統(tǒng)計(jì)類問題里溢出的坑集中出現(xiàn)在兩個(gè)地方逆序?qū)?shù)量和小和累加值。逆序?qū)?shù)量最大是 n(n-1)/2n10^5 時(shí)就達(dá)到約 5 × 10^9必須用long long。小和問題的累加值更夸張如果一個(gè)元素值是 10^9它在最壞情況下可能被累加 n 次總和的量級(jí)是 10^14連 int 的一個(gè)零頭都裝不下。不僅變量類型要注意乘法的中間結(jié)果也要轉(zhuǎn)類型。arr[i] * (right - j 1)如果兩個(gè)操作數(shù)都是 int乘法結(jié)果直接溢出賦值給 long long 也救不回來。正確寫法是(long long)arr[i] * (right - j 1)先把一邊轉(zhuǎn)成 long long整個(gè)表達(dá)式自動(dòng)提升為 long long 運(yùn)算。我在實(shí)際解題中多次因?yàn)檫@些問題返工。分治本身不難難的是各種邊界和類型細(xì)節(jié)。寫完代碼后一定自己構(gòu)造幾組數(shù)據(jù)測一下空數(shù)組、單元素、全部相等、完全逆序、完全有序。這些邊界案例跑一遍比你在編譯器里反復(fù)看代碼管用得多。最后再分享一個(gè)小技巧調(diào)試分治代碼時(shí)最好加一個(gè)打印函數(shù)把每層遞歸處理的區(qū)間 [left, mid, right] 和合并后的數(shù)組打印出來。這樣你能直觀看到遞歸是否按預(yù)期拆解合并是否真的有序。我過去調(diào)試歸并二進(jìn)制轉(zhuǎn)儲(chǔ)數(shù)據(jù)時(shí)靠這個(gè)手段十分鐘就定位到了問題省去了兩小時(shí)的懷疑人生。