τ嫈?shù)：歸并排序的O(n log n)解法與Go實現(xiàn))
1. 逆序?qū)Φ亩x為什么這一題能攔住很多人我第一次認(rèn)真接觸“逆序?qū)Α笔窃谔幚硪慌判蚪y(tǒng)計相關(guān)的小工具時。當(dāng)時我需要量化一組序列到底“有多亂”排序本身只能給出結(jié)果順序卻丟失了原始亂序程度。后來才意識到逆序?qū)?shù)量正好是一個可以精確描述亂序程度的指標(biāo)對于一個數(shù)組nums只要下標(biāo)i j并且nums[i] nums[j]這一對元素就叫一個逆序?qū)?。完全升序的?shù)組逆序?qū)?shù)量是 0完全降序的數(shù)組逆序?qū)?shù)量是n*(n-1)/2也就是任意兩個元素都能構(gòu)成逆序?qū)Α＿@個定義說起來一句話的事但真正做起來卻很考驗對分治算法的理解。很多人在這一題上卡住并不是因為不知道規(guī)則而是遇到大數(shù)組時第一反應(yīng)只會寫兩層循環(huán)。面試?yán)镆步?jīng)常問這道題它的本意不是考察你會不會枚舉所有數(shù)對而是考察你能不能把統(tǒng)計過程融進(jìn)排序過程里做到 O(n log n) 的時間復(fù)雜度。1.1 一個例子把定義說清楚拿[3, 1, 2]來舉例。數(shù)組下標(biāo)從 0 開始三個元素能組成三對下標(biāo)(0, 1)3和1因為3 1構(gòu)成逆序?qū)?0, 2)3和2因為3 2構(gòu)成逆序?qū)?1, 2)1和2因為1 2不構(gòu)成逆序?qū)?。所以這個數(shù)組的逆序?qū)倲?shù)是 2。這個例子看起來過于簡單但里面藏著最容易被忽略的點逆序?qū)Σ皇强疾炷硞€元素本身有多大而是考察兩個元素的相對位置和相對大小是否顛倒。一個很大的元素出現(xiàn)在數(shù)組靠前的位置它可能和后面好幾個元素構(gòu)成逆序?qū)σ粋€很小的元素出現(xiàn)在靠后的位置它可能和前面好幾個元素構(gòu)成逆序?qū)Α?.2 逆序?qū)蛿?shù)組亂序程度的關(guān)系逆序?qū)Φ臄?shù)量在數(shù)學(xué)上可以直接反映亂序程度但它又不是一個線性指標(biāo)。升序數(shù)組是 0降序數(shù)組是n*(n-1)/2中間任意亂序數(shù)組的數(shù)量則落在兩者之間。換句話說它是衡量序列無序度的一種“距離”度量和“把這個數(shù)組穩(wěn)定排序需要移動多少元素”直接相關(guān)。我在后來的很多場景里發(fā)現(xiàn)這個概念并不只是面試題數(shù)據(jù)完整性校驗、排序后相對次序變化分析、以及一些推薦排序里的擾動檢測都會用到逆序?qū)蛘咚淖兎N。理解清楚它的數(shù)學(xué)性質(zhì)比單純背答案有用得多。2. 暴力解法能跑但跑不出規(guī)模如果不知道優(yōu)化思路絕大多數(shù)人的第一反應(yīng)都是直接枚舉。兩層循環(huán)外層固定左側(cè)元素內(nèi)層遍歷右側(cè)元素一旦發(fā)現(xiàn)左側(cè)大于右側(cè)計數(shù)加一。這個解法完全沒錯而且在小數(shù)據(jù)量下還可以作為驗證工具。2.1 雙層循環(huán)的直白版本暴力版本在 Go 里面寫起來很簡潔func bruteForceCount(nums []int) int64 { var count int64 for i : 0; i len(nums); i { for j : i 1; j len(nums); j { if nums[i] nums[j] { count } } } return count }注意我把返回值定義成了int64原因是逆序?qū)?shù)量的上限是n*(n-1)/2當(dāng)數(shù)組長度為 100000 時理論最大值已經(jīng)接近 50 億普通 32 位整數(shù)很可能裝不下。從第一版代碼就使用 64 位整數(shù)可以少踩一個非常隱蔽的坑。2.2 規(guī)模大了以后會發(fā)生什么暴力解法的時間復(fù)雜度是 O(n^2)。假設(shè)一臺機(jī)器每秒能執(zhí)行大約一億次基本比較當(dāng)數(shù)組長度來到 10000大約需要執(zhí)行 5000 萬次比較肉眼可能還能接受當(dāng)長度來到 100000需要執(zhí)行 50 億次比較運(yùn)行時間會從毫秒級直接跨到秒級甚至更久再往上到 1000000那就是災(zāi)難。我在實際測試時用隨機(jī)數(shù)組跑過兩個版本的對比。長度 1 萬以內(nèi)暴力版和歸并版幾乎看不出差距長度 10 萬時暴力版已經(jīng)明顯卡頓而歸并版仍然在個位數(shù)毫秒級別。這里想說的并不是暴力版“一無是處”相反它非常適合做基準(zhǔn)驗證我先用暴力版算出正確答案再拿歸并版去對照能快速確定優(yōu)化版本有沒有寫錯。我到現(xiàn)在都習(xí)慣把暴力版留在測試代碼里作為交叉驗證的基準(zhǔn)。還有一個容易被忽略的點暴力版會真實地枚舉所有數(shù)對所以它對任何規(guī)模的數(shù)據(jù)都能給出確定結(jié)果不存在遞歸深度、邊界處理之類的問題。因此在小數(shù)組的單元測試中用暴力版做標(biāo)準(zhǔn)答案是非常穩(wěn)妥的策略。3. 歸并排序解法把計數(shù)融進(jìn)排序過程的三個關(guān)鍵點既然暴力解法在數(shù)據(jù)規(guī)模變大以后不現(xiàn)實那就要找一種只排序、不枚舉所有數(shù)對的方法。這里核心思路來自歸并排序在合并兩個有序子數(shù)組的過程中順帶統(tǒng)計跨子數(shù)組的逆序?qū)Α?.1 從“比較所有數(shù)對”到“只在合并時數(shù)”歸并排序的本質(zhì)是分治先把數(shù)組從中間拆成左右兩半分別排序再合并。一個逆序?qū)χ械膬蓚€元素只可能有兩種位置關(guān)系都在左半部分都在右半部分或者一個在左、一個在右。前兩種情況會被遞歸子問題覆蓋第三種情況只在合并這一步發(fā)生。所以我可以把問題拆成三部分統(tǒng)計左半部分內(nèi)部的逆序?qū)由嫌野氩糠謨?nèi)部的逆序?qū)υ偌由献笥覂砂胫g形成的逆序?qū)?。遞歸能解決前兩部分合并時只需要重點處理第三部分。這個“分治”視角和暴力枚舉完全不同暴力枚舉把每一對都看作獨(dú)立個體而歸并解法把大量比較壓縮到了合并階段。因此整個算法的時間復(fù)雜度從 O(n^2) 下降到 O(n log n)。這也是歸并排序本身的能力每一層所有子區(qū)間合并的總工作量是 O(n)遞歸深度是 O(log n)所以總工作量是 O(n log n)。3.2 (mid - i 1) 是怎么算出來的這是全題最關(guān)鍵的一行代碼也是我在初次實現(xiàn)時最容易寫錯的地方。先看合并過程本身兩個子數(shù)組都已經(jīng)有序左邊是arr[left:mid1]右邊是arr[mid1:right1]合并時用兩個指針i和j分別指向當(dāng)前左右元素誰小先放入臨時數(shù)組。關(guān)鍵判斷發(fā)生在arr[i] arr[j]時。由于左邊子數(shù)組內(nèi)部是有序遞增的從i到mid的所有元素都大于等于arr[i]而arr[i]已經(jīng)大于arr[j]那么從i到mid的全部元素都一定大于arr[j]。也就是說arr[j]和左邊剩余的這一批元素每一對都構(gòu)成逆序?qū)?shù)量正好是mid - i 1。一句讓很多人困惑的話是“為什么不是只加 1”因為當(dāng)前這一步取了右邊的arr[j]說明右邊的這個元素小于左邊當(dāng)前指針指向的元素?？勺筮呏羔樅竺娴脑馗笏鼈冏匀灰捕即笥谶@個右邊的元素。這幾個逆序?qū)υ谶@一步被批量統(tǒng)計了等指針再往后走這些元素就再也不會和同一個右邊的arr[j]組成任何新對因此不會漏計也不會重復(fù)計。等號的處理也要特別留意如果arr[i] arr[j]說明左邊元素不大于右邊元素此時不構(gòu)成逆序?qū)ΑＨ绻`寫成會把相等的兩個元素也當(dāng)成逆序?qū)?。這個問題在重復(fù)元素很多的數(shù)組中會直接導(dǎo)致答案錯誤。3.3 用手算子數(shù)組推演一遍 [7,5,6,4]我每次學(xué)這一類算法都習(xí)慣拿一個小數(shù)組完整推演光看代碼容易云里霧里。這里用[7, 5, 6, 4]來驗證上面的邏輯。第一步從中間拆開左半部分[7, 5]右半部分[6, 4]。先遞歸處理左半部分[7, 5]再拆成[7]和[5]合并時7 5加 1得到排序后的[5, 7]。再遞歸處理右半部分[6, 4]拆成[6]和[4]合并時6 4加 1得到排序后的[4, 6]?，F(xiàn)在進(jìn)入最后的合并左邊是[5, 7]右邊是[4, 6]比較5和4因為5 4加mid - i 1此時左邊從5到末尾有兩個元素所以加 2同時取走右邊的4比較5和65 6取走左邊的5比較7和67 6此時左邊剩余元素只有7加 1取走右邊的6左邊剩余7直接放入臨時數(shù)組。總計數(shù)是1 1 2 1 5。再暴力枚舉驗證一下[7,5]、[7,6]、[7,4]、[5,4]、[6,4]正好 5 個沒有誤計。這個推演過程理解透了代碼就很難寫錯。4. Go 源碼實現(xiàn)與逐段注釋語言本身也會影響這類算法的寫法。Go 的切片、遞歸和內(nèi)存分配機(jī)制和 C 或 Java 主流的寫法有一些微妙差異。這里給出一個我能直接放到項目里用的完整實現(xiàn)。4.1 完整源碼package inversion // InversePairs 統(tǒng)計數(shù)組中的逆序?qū)?shù)量。 // 返回值使用 int64避免數(shù)組較大時計數(shù)溢出。 func InversePairs(nums []int) int64 { // 拷貝一份輸入數(shù)據(jù)保證原數(shù)組不被排序過程改動 arr : make([]int, len(nums)) copy(arr, nums) // 臨時數(shù)組只在最外層分配一次 tmp : make([]int, len(arr)) return mergeSortAndCount(arr, tmp, 0, len(arr)-1) } func mergeSortAndCount(arr, tmp []int, left, right int) int64 { if left right { return 0 } mid : left (right-left)/2 var count int64 // 左半部分內(nèi)部的逆序?qū)?count mergeSortAndCount(arr, tmp, left, mid) // 右半部分內(nèi)部的逆序?qū)?count mergeSortAndCount(arr, tmp, mid1, right) // 跨越左右兩部分的逆序?qū)?count mergeAndCount(arr, tmp, left, mid, right) return count } func mergeAndCount(arr, tmp []int, left, mid, right int) int64 { i : left // 左子數(shù)組指針 j : mid 1 // 右子數(shù)組指針 k : left // 臨時數(shù)組指針 var count int64 for i mid j right { if arr[i] arr[j] { tmp[k] arr[i] i } else { tmp[k] arr[j] // 關(guān)鍵計數(shù)左邊從 i 到 mid 的所有元素都大于 arr[j] count int64(mid - i 1) j } k } // 剩余元素直接拷貝 for i mid { tmp[k] arr[i] i k } for j right { tmp[k] arr[j] j k } // 把排序結(jié)果寫回原切片保證遞歸上層能看到有序結(jié)果 copy(arr[left:right1], tmp[left:right1]) return count }4.2 三個值得多花時間看的設(shè)計點第一個設(shè)計點是臨時數(shù)組的分配策略。很多初學(xué)版本會在每次遞歸合并時新建make([]int, ...)結(jié)果會產(chǎn)生 O(n log n) 次分配雖然算法復(fù)雜度沒變但內(nèi)存分配帶來的開銷非常明顯。我在上面的實現(xiàn)里只在最外層創(chuàng)建一次tmp遞歸全程復(fù)用同一塊切片。這樣可以把額外空間控制在 O(n)。第二個設(shè)計點是left (right-left)/2而不是(leftright)/2。在左右邊界都很大的情況下后一種寫法可能因為整數(shù)加法溢出導(dǎo)致 mid 算錯。Go 的 int 在 64 位平臺是 64 位能容納很大的數(shù)組長度但用前一種寫法是更穩(wěn)妥的習(xí)慣也能避免邊界計算中的細(xì)小問題。第三個設(shè)計點是遞歸邊界left right。這個條件看似簡單卻在數(shù)組為空時特別關(guān)鍵。當(dāng)InversePairs接收到空數(shù)組時初始調(diào)用right -1此時left(0) right(-1)函數(shù)直接返回 0不會出現(xiàn)切片越界。很多初學(xué)者會寫成left right遇到空數(shù)組就會直接 panic。4.3 時間空間的實際代價這個實現(xiàn)的時間復(fù)雜度是 O(n log n)空間復(fù)雜度 O(n)。但實際運(yùn)行時的常數(shù)開銷比我想象中要小不少因為切片拷貝使用 Go 底層的內(nèi)存復(fù)制合并過程是線性掃描沒有額外復(fù)雜操作。我在測試數(shù)據(jù)規(guī)模 100 萬亂序整數(shù)時單次調(diào)用大約在幾百毫秒級別具體取決于機(jī)器。這個規(guī)模下暴力版本基本已經(jīng)等不到結(jié)果了。如果數(shù)據(jù)量繼續(xù)增大到幾千萬我會考慮換成迭代式歸并排序規(guī)避遞歸函數(shù)調(diào)用的開銷不過那是另一個優(yōu)化話題普通業(yè)務(wù)場景里用上面的遞歸版本已經(jīng)足夠穩(wěn)定。5. 測試用例與邊界條件寫這類函數(shù)最容易翻車的地方算法寫完不等于萬事大吉。逆序?qū)@類函數(shù)邊界條件多重復(fù)數(shù)據(jù)多稍微不注意就會出現(xiàn)“小數(shù)據(jù)全對大數(shù)據(jù)全錯”的詭異現(xiàn)象。5.1 用 Go 測試函數(shù)把正確性鎖住我用 Go 內(nèi)置的testing包寫一組固定測試用例配合暴力版交叉驗證。package inversion import ( math/rand testing ) func bruteForceCount(nums []int) int64 { var count int64 for i : 0; i len(nums); i { for j : i 1; j len(nums); j { if nums[i] nums[j] { count } } } return count } func TestInversePairs(t *testing.T) { cases : []struct { name string data []int want int64 }{ {空數(shù)組, []int{}, 0}, {單個元素, []int{1}, 0}, {完全升序, []int{1, 2, 3, 4, 5}, 0}, {完全降序, []int{5, 4, 3, 2, 1}, 10}, {經(jīng)典例子, []int{3, 1, 2}, 2}, {重復(fù)元素, []int{2, 2, 1, 1}, 4}, } for _, tc : range cases { t.Run(tc.name, func(t *testing.T) { if got : InversePairs(tc.data); got ! tc.want { t.Fatalf(got %d, want %d, got, tc.want) } }) } }固定用例之外更重要的是隨機(jī)交叉驗證。我會生成長度從 0 到 50 的隨機(jī)數(shù)組分別用暴力版和歸并版計算只要結(jié)果不一致就立刻定位問題。func TestRandomCrossCheck(t *testing.T) { rng : rand.New(rand.NewSource(20250401)) for n : 0; n 50; n { data : make([]int, n) for i : range data { data[i] rng.Intn(100) } original : make([]int, n) copy(original, data) want : bruteForceCount(data) got : InversePairs(data) if got ! want { t.Fatalf(n%d data%v got%d want%d, n, data, got, want) } for i : range data { if data[i] ! original[i] { t.Fatalf(input modified: got %v want %v, data, original) } } } }這個隨機(jī)測試?yán)镂疫€順帶校驗了一件事調(diào)用完InversePairs后原數(shù)組沒有被排序過程改掉。因為我先拷貝了輸入所以這個檢查一定通過如果實現(xiàn)里直接拿外部切片排序這個測試就會立刻報警。5.2 重復(fù)元素導(dǎo)致的最大坑相等到底算不算很多人的第一版實現(xiàn)會把a(bǔ)rr[i] arr[j]寫成arr[i] arr[j]導(dǎo)致相等的兩個元素被當(dāng)成逆序?qū)?。比如[2, 2]規(guī)范答案是 0因為2并不大于2但如果比較條件寫錯會統(tǒng)計成 1。這個問題在包含大量重復(fù)值的業(yè)務(wù)數(shù)據(jù)中非常致命。我一開始也踩過這個坑測試數(shù)據(jù)全是隨機(jī)整數(shù)很少在意重復(fù)值是否統(tǒng)計正確。后來加了一組包含大量重復(fù)元素的壓測用例才暴露出來。所以我在固定用例里特意寫了{(lán)重復(fù)元素, []int{2, 2, 1, 1}, 4}就是要保證相等元素不會被誤計。5.3 別改動入?yún)⒊悄阌忻鞔_理由歸并排序天然會改變原數(shù)組順序。在純粹刷題場景里改掉傳入數(shù)組可能無所謂但在工程項目中調(diào)用方往往還持有這份數(shù)據(jù)做后續(xù)計算一旦被排序后續(xù)邏輯全亂。我建議的默認(rèn)做法是在入口處拷貝一次輸入。雖然多出 O(n) 的拷貝時間但能換來非?？少F的確定性。上面的源碼也是這么做的。如果對性能極其敏感可以在文檔里明確標(biāo)注“此函數(shù)會修改輸入數(shù)組”再把拷貝去掉但這應(yīng)該是一個顯式?jīng)Q策而不是順手寫出來的副作用。6. 這道題的后續(xù)延伸它不只是面試題逆序?qū)Φ臍w并解法掌握以后能遷移到不少看起來不相干的題目上。比如“計算數(shù)組中有多少對元素滿足某種偏序關(guān)系”“求兩個排列之間的相似度”甚至某些推薦排序場景里的亂序程度評估背后都是同一套分治計數(shù)思想。每次遇到新的“成對計數(shù)”問題我都會先問一句能不能在排序的過程中順便統(tǒng)計如果能那大概率就是歸并排序變種。6.1 從逆序?qū)Φ狡驅(qū)栴}的想象力如果把“逆序?qū)Α钡呐卸l件從nums[i] nums[j]換成其他比較規(guī)則比如nums[i] 2 * nums[j]或者附帶一些額外結(jié)構(gòu)體字段比較算法框架仍然成立。真正需要修改的只是合并時的判斷條件和計數(shù)公式。理解到這一層題目就不再是背模板而是變成一種“排序時批量處理相對關(guān)系”的思維工具。6.2 我檢查這類代碼的經(jīng)驗我現(xiàn)在寫這類函數(shù)一定會先跑三件事用空數(shù)組、長度為 1 的數(shù)組驗證越界問題用完全升序和完全降序的數(shù)組驗證計數(shù)的上下邊界用包含重復(fù)元素的數(shù)組驗證等號條件。這三個都過了再拿暴力版做隨機(jī)交叉驗證。很多邊界問題比如 Go 切片索引、遞歸終止條件、計數(shù)溢出都能在這一套流程里暴露出來。這套流程看起來很簡單但能在很長時間里幫我少走彎路。 逆序?qū)τ嫈?shù)：歸并排序的O(n log n)解法與Go實現(xiàn)
1. 逆序?qū)Φ亩x為什么這一題能攔住很多人我第一次認(rèn)真接觸“逆序?qū)Α笔窃谔幚硪慌判蚪y(tǒng)計相關(guān)的小工具時。當(dāng)時我需要量化一組序列到底“有多亂”排序本身只能給出結(jié)果順序卻丟失了原始亂序程度。后來才意識到逆序?qū)?shù)量正好是一個可以精確描述亂序程度的指標(biāo)對于一個數(shù)組nums只要下標(biāo)i j并且nums[i] nums[j]這一對元素就叫一個逆序?qū)?。完全升序的?shù)組逆序?qū)?shù)量是 0完全降序的數(shù)組逆序?qū)?shù)量是n*(n-1)/2也就是任意兩個元素都能構(gòu)成逆序?qū)Α＿@個定義說起來一句話的事但真正做起來卻很考驗對分治算法的理解。很多人在這一題上卡住并不是因為不知道規(guī)則而是遇到大數(shù)組時第一反應(yīng)只會寫兩層循環(huán)。面試?yán)镆步?jīng)常問這道題它的本意不是考察你會不會枚舉所有數(shù)對而是考察你能不能把統(tǒng)計過程融進(jìn)排序過程里做到 O(n log n) 的時間復(fù)雜度。1.1 一個例子把定義說清楚拿[3, 1, 2]來舉例。數(shù)組下標(biāo)從 0 開始三個元素能組成三對下標(biāo)(0, 1)3和1因為3 1構(gòu)成逆序?qū)?0, 2)3和2因為3 2構(gòu)成逆序?qū)?1, 2)1和2因為1 2不構(gòu)成逆序?qū)?。所以這個數(shù)組的逆序?qū)倲?shù)是 2。這個例子看起來過于簡單但里面藏著最容易被忽略的點逆序?qū)Σ皇强疾炷硞€元素本身有多大而是考察兩個元素的相對位置和相對大小是否顛倒。一個很大的元素出現(xiàn)在數(shù)組靠前的位置它可能和后面好幾個元素構(gòu)成逆序?qū)σ粋€很小的元素出現(xiàn)在靠后的位置它可能和前面好幾個元素構(gòu)成逆序?qū)Α?.2 逆序?qū)蛿?shù)組亂序程度的關(guān)系逆序?qū)Φ臄?shù)量在數(shù)學(xué)上可以直接反映亂序程度但它又不是一個線性指標(biāo)。升序數(shù)組是 0降序數(shù)組是n*(n-1)/2中間任意亂序數(shù)組的數(shù)量則落在兩者之間。換句話說它是衡量序列無序度的一種“距離”度量和“把這個數(shù)組穩(wěn)定排序需要移動多少元素”直接相關(guān)。我在后來的很多場景里發(fā)現(xiàn)這個概念并不只是面試題數(shù)據(jù)完整性校驗、排序后相對次序變化分析、以及一些推薦排序里的擾動檢測都會用到逆序?qū)蛘咚淖兎N。理解清楚它的數(shù)學(xué)性質(zhì)比單純背答案有用得多。2. 暴力解法能跑但跑不出規(guī)模如果不知道優(yōu)化思路絕大多數(shù)人的第一反應(yīng)都是直接枚舉。兩層循環(huán)外層固定左側(cè)元素內(nèi)層遍歷右側(cè)元素一旦發(fā)現(xiàn)左側(cè)大于右側(cè)計數(shù)加一。這個解法完全沒錯而且在小數(shù)據(jù)量下還可以作為驗證工具。2.1 雙層循環(huán)的直白版本暴力版本在 Go 里面寫起來很簡潔func bruteForceCount(nums []int) int64 { var count int64 for i : 0; i len(nums); i { for j : i 1; j len(nums); j { if nums[i] nums[j] { count } } } return count }注意我把返回值定義成了int64原因是逆序?qū)?shù)量的上限是n*(n-1)/2當(dāng)數(shù)組長度為 100000 時理論最大值已經(jīng)接近 50 億普通 32 位整數(shù)很可能裝不下。從第一版代碼就使用 64 位整數(shù)可以少踩一個非常隱蔽的坑。2.2 規(guī)模大了以后會發(fā)生什么暴力解法的時間復(fù)雜度是 O(n^2)。假設(shè)一臺機(jī)器每秒能執(zhí)行大約一億次基本比較當(dāng)數(shù)組長度來到 10000大約需要執(zhí)行 5000 萬次比較肉眼可能還能接受當(dāng)長度來到 100000需要執(zhí)行 50 億次比較運(yùn)行時間會從毫秒級直接跨到秒級甚至更久再往上到 1000000那就是災(zāi)難。我在實際測試時用隨機(jī)數(shù)組跑過兩個版本的對比。長度 1 萬以內(nèi)暴力版和歸并版幾乎看不出差距長度 10 萬時暴力版已經(jīng)明顯卡頓而歸并版仍然在個位數(shù)毫秒級別。這里想說的并不是暴力版“一無是處”相反它非常適合做基準(zhǔn)驗證我先用暴力版算出正確答案再拿歸并版去對照能快速確定優(yōu)化版本有沒有寫錯。我到現(xiàn)在都習(xí)慣把暴力版留在測試代碼里作為交叉驗證的基準(zhǔn)。還有一個容易被忽略的點暴力版會真實地枚舉所有數(shù)對所以它對任何規(guī)模的數(shù)據(jù)都能給出確定結(jié)果不存在遞歸深度、邊界處理之類的問題。因此在小數(shù)組的單元測試中用暴力版做標(biāo)準(zhǔn)答案是非常穩(wěn)妥的策略。3. 歸并排序解法把計數(shù)融進(jìn)排序過程的三個關(guān)鍵點既然暴力解法在數(shù)據(jù)規(guī)模變大以后不現(xiàn)實那就要找一種只排序、不枚舉所有數(shù)對的方法。這里核心思路來自歸并排序在合并兩個有序子數(shù)組的過程中順帶統(tǒng)計跨子數(shù)組的逆序?qū)Α?.1 從“比較所有數(shù)對”到“只在合并時數(shù)”歸并排序的本質(zhì)是分治先把數(shù)組從中間拆成左右兩半分別排序再合并。一個逆序?qū)χ械膬蓚€元素只可能有兩種位置關(guān)系都在左半部分都在右半部分或者一個在左、一個在右。前兩種情況會被遞歸子問題覆蓋第三種情況只在合并這一步發(fā)生。所以我可以把問題拆成三部分統(tǒng)計左半部分內(nèi)部的逆序?qū)由嫌野氩糠謨?nèi)部的逆序?qū)υ偌由献笥覂砂胫g形成的逆序?qū)?。遞歸能解決前兩部分合并時只需要重點處理第三部分。這個“分治”視角和暴力枚舉完全不同暴力枚舉把每一對都看作獨(dú)立個體而歸并解法把大量比較壓縮到了合并階段。因此整個算法的時間復(fù)雜度從 O(n^2) 下降到 O(n log n)。這也是歸并排序本身的能力每一層所有子區(qū)間合并的總工作量是 O(n)遞歸深度是 O(log n)所以總工作量是 O(n log n)。3.2 (mid - i 1) 是怎么算出來的這是全題最關(guān)鍵的一行代碼也是我在初次實現(xiàn)時最容易寫錯的地方。先看合并過程本身兩個子數(shù)組都已經(jīng)有序左邊是arr[left:mid1]右邊是arr[mid1:right1]合并時用兩個指針i和j分別指向當(dāng)前左右元素誰小先放入臨時數(shù)組。關(guān)鍵判斷發(fā)生在arr[i] arr[j]時。由于左邊子數(shù)組內(nèi)部是有序遞增的從i到mid的所有元素都大于等于arr[i]而arr[i]已經(jīng)大于arr[j]那么從i到mid的全部元素都一定大于arr[j]。也就是說arr[j]和左邊剩余的這一批元素每一對都構(gòu)成逆序?qū)?shù)量正好是mid - i 1。一句讓很多人困惑的話是“為什么不是只加 1”因為當(dāng)前這一步取了右邊的arr[j]說明右邊的這個元素小于左邊當(dāng)前指針指向的元素?？勺筮呏羔樅竺娴脑馗笏鼈冏匀灰捕即笥谶@個右邊的元素。這幾個逆序?qū)υ谶@一步被批量統(tǒng)計了等指針再往后走這些元素就再也不會和同一個右邊的arr[j]組成任何新對因此不會漏計也不會重復(fù)計。等號的處理也要特別留意如果arr[i] arr[j]說明左邊元素不大于右邊元素此時不構(gòu)成逆序?qū)ΑＨ绻`寫成會把相等的兩個元素也當(dāng)成逆序?qū)?。這個問題在重復(fù)元素很多的數(shù)組中會直接導(dǎo)致答案錯誤。3.3 用手算子數(shù)組推演一遍 [7,5,6,4]我每次學(xué)這一類算法都習(xí)慣拿一個小數(shù)組完整推演光看代碼容易云里霧里。這里用[7, 5, 6, 4]來驗證上面的邏輯。第一步從中間拆開左半部分[7, 5]右半部分[6, 4]。先遞歸處理左半部分[7, 5]再拆成[7]和[5]合并時7 5加 1得到排序后的[5, 7]。再遞歸處理右半部分[6, 4]拆成[6]和[4]合并時6 4加 1得到排序后的[4, 6]?，F(xiàn)在進(jìn)入最后的合并左邊是[5, 7]右邊是[4, 6]比較5和4因為5 4加mid - i 1此時左邊從5到末尾有兩個元素所以加 2同時取走右邊的4比較5和65 6取走左邊的5比較7和67 6此時左邊剩余元素只有7加 1取走右邊的6左邊剩余7直接放入臨時數(shù)組。總計數(shù)是1 1 2 1 5。再暴力枚舉驗證一下[7,5]、[7,6]、[7,4]、[5,4]、[6,4]正好 5 個沒有誤計。這個推演過程理解透了代碼就很難寫錯。4. Go 源碼實現(xiàn)與逐段注釋語言本身也會影響這類算法的寫法。Go 的切片、遞歸和內(nèi)存分配機(jī)制和 C 或 Java 主流的寫法有一些微妙差異。這里給出一個我能直接放到項目里用的完整實現(xiàn)。4.1 完整源碼package inversion // InversePairs 統(tǒng)計數(shù)組中的逆序?qū)?shù)量。 // 返回值使用 int64避免數(shù)組較大時計數(shù)溢出。 func InversePairs(nums []int) int64 { // 拷貝一份輸入數(shù)據(jù)保證原數(shù)組不被排序過程改動 arr : make([]int, len(nums)) copy(arr, nums) // 臨時數(shù)組只在最外層分配一次 tmp : make([]int, len(arr)) return mergeSortAndCount(arr, tmp, 0, len(arr)-1) } func mergeSortAndCount(arr, tmp []int, left, right int) int64 { if left right { return 0 } mid : left (right-left)/2 var count int64 // 左半部分內(nèi)部的逆序?qū)?count mergeSortAndCount(arr, tmp, left, mid) // 右半部分內(nèi)部的逆序?qū)?count mergeSortAndCount(arr, tmp, mid1, right) // 跨越左右兩部分的逆序?qū)?count mergeAndCount(arr, tmp, left, mid, right) return count } func mergeAndCount(arr, tmp []int, left, mid, right int) int64 { i : left // 左子數(shù)組指針 j : mid 1 // 右子數(shù)組指針 k : left // 臨時數(shù)組指針 var count int64 for i mid j right { if arr[i] arr[j] { tmp[k] arr[i] i } else { tmp[k] arr[j] // 關(guān)鍵計數(shù)左邊從 i 到 mid 的所有元素都大于 arr[j] count int64(mid - i 1) j } k } // 剩余元素直接拷貝 for i mid { tmp[k] arr[i] i k } for j right { tmp[k] arr[j] j k } // 把排序結(jié)果寫回原切片保證遞歸上層能看到有序結(jié)果 copy(arr[left:right1], tmp[left:right1]) return count }4.2 三個值得多花時間看的設(shè)計點第一個設(shè)計點是臨時數(shù)組的分配策略。很多初學(xué)版本會在每次遞歸合并時新建make([]int, ...)結(jié)果會產(chǎn)生 O(n log n) 次分配雖然算法復(fù)雜度沒變但內(nèi)存分配帶來的開銷非常明顯。我在上面的實現(xiàn)里只在最外層創(chuàng)建一次tmp遞歸全程復(fù)用同一塊切片。這樣可以把額外空間控制在 O(n)。第二個設(shè)計點是left (right-left)/2而不是(leftright)/2。在左右邊界都很大的情況下后一種寫法可能因為整數(shù)加法溢出導(dǎo)致 mid 算錯。Go 的 int 在 64 位平臺是 64 位能容納很大的數(shù)組長度但用前一種寫法是更穩(wěn)妥的習(xí)慣也能避免邊界計算中的細(xì)小問題。第三個設(shè)計點是遞歸邊界left right。這個條件看似簡單卻在數(shù)組為空時特別關(guān)鍵。當(dāng)InversePairs接收到空數(shù)組時初始調(diào)用right -1此時left(0) right(-1)函數(shù)直接返回 0不會出現(xiàn)切片越界。很多初學(xué)者會寫成left right遇到空數(shù)組就會直接 panic。4.3 時間空間的實際代價這個實現(xiàn)的時間復(fù)雜度是 O(n log n)空間復(fù)雜度 O(n)。但實際運(yùn)行時的常數(shù)開銷比我想象中要小不少因為切片拷貝使用 Go 底層的內(nèi)存復(fù)制合并過程是線性掃描沒有額外復(fù)雜操作。我在測試數(shù)據(jù)規(guī)模 100 萬亂序整數(shù)時單次調(diào)用大約在幾百毫秒級別具體取決于機(jī)器。這個規(guī)模下暴力版本基本已經(jīng)等不到結(jié)果了。如果數(shù)據(jù)量繼續(xù)增大到幾千萬我會考慮換成迭代式歸并排序規(guī)避遞歸函數(shù)調(diào)用的開銷不過那是另一個優(yōu)化話題普通業(yè)務(wù)場景里用上面的遞歸版本已經(jīng)足夠穩(wěn)定。5. 測試用例與邊界條件寫這類函數(shù)最容易翻車的地方算法寫完不等于萬事大吉。逆序?qū)@類函數(shù)邊界條件多重復(fù)數(shù)據(jù)多稍微不注意就會出現(xiàn)“小數(shù)據(jù)全對大數(shù)據(jù)全錯”的詭異現(xiàn)象。5.1 用 Go 測試函數(shù)把正確性鎖住我用 Go 內(nèi)置的testing包寫一組固定測試用例配合暴力版交叉驗證。package inversion import ( math/rand testing ) func bruteForceCount(nums []int) int64 { var count int64 for i : 0; i len(nums); i { for j : i 1; j len(nums); j { if nums[i] nums[j] { count } } } return count } func TestInversePairs(t *testing.T) { cases : []struct { name string data []int want int64 }{ {空數(shù)組, []int{}, 0}, {單個元素, []int{1}, 0}, {完全升序, []int{1, 2, 3, 4, 5}, 0}, {完全降序, []int{5, 4, 3, 2, 1}, 10}, {經(jīng)典例子, []int{3, 1, 2}, 2}, {重復(fù)元素, []int{2, 2, 1, 1}, 4}, } for _, tc : range cases { t.Run(tc.name, func(t *testing.T) { if got : InversePairs(tc.data); got ! tc.want { t.Fatalf(got %d, want %d, got, tc.want) } }) } }固定用例之外更重要的是隨機(jī)交叉驗證。我會生成長度從 0 到 50 的隨機(jī)數(shù)組分別用暴力版和歸并版計算只要結(jié)果不一致就立刻定位問題。func TestRandomCrossCheck(t *testing.T) { rng : rand.New(rand.NewSource(20250401)) for n : 0; n 50; n { data : make([]int, n) for i : range data { data[i] rng.Intn(100) } original : make([]int, n) copy(original, data) want : bruteForceCount(data) got : InversePairs(data) if got ! want { t.Fatalf(n%d data%v got%d want%d, n, data, got, want) } for i : range data { if data[i] ! original[i] { t.Fatalf(input modified: got %v want %v, data, original) } } } }這個隨機(jī)測試?yán)镂疫€順帶校驗了一件事調(diào)用完InversePairs后原數(shù)組沒有被排序過程改掉。因為我先拷貝了輸入所以這個檢查一定通過如果實現(xiàn)里直接拿外部切片排序這個測試就會立刻報警。5.2 重復(fù)元素導(dǎo)致的最大坑相等到底算不算很多人的第一版實現(xiàn)會把a(bǔ)rr[i] arr[j]寫成arr[i] arr[j]導(dǎo)致相等的兩個元素被當(dāng)成逆序?qū)?。比如[2, 2]規(guī)范答案是 0因為2并不大于2但如果比較條件寫錯會統(tǒng)計成 1。這個問題在包含大量重復(fù)值的業(yè)務(wù)數(shù)據(jù)中非常致命。我一開始也踩過這個坑測試數(shù)據(jù)全是隨機(jī)整數(shù)很少在意重復(fù)值是否統(tǒng)計正確。后來加了一組包含大量重復(fù)元素的壓測用例才暴露出來。所以我在固定用例里特意寫了{(lán)重復(fù)元素, []int{2, 2, 1, 1}, 4}就是要保證相等元素不會被誤計。5.3 別改動入?yún)⒊悄阌忻鞔_理由歸并排序天然會改變原數(shù)組順序。在純粹刷題場景里改掉傳入數(shù)組可能無所謂但在工程項目中調(diào)用方往往還持有這份數(shù)據(jù)做后續(xù)計算一旦被排序后續(xù)邏輯全亂。我建議的默認(rèn)做法是在入口處拷貝一次輸入。雖然多出 O(n) 的拷貝時間但能換來非?？少F的確定性。上面的源碼也是這么做的。如果對性能極其敏感可以在文檔里明確標(biāo)注“此函數(shù)會修改輸入數(shù)組”再把拷貝去掉但這應(yīng)該是一個顯式?jīng)Q策而不是順手寫出來的副作用。6. 這道題的后續(xù)延伸它不只是面試題逆序?qū)Φ臍w并解法掌握以后能遷移到不少看起來不相干的題目上。比如“計算數(shù)組中有多少對元素滿足某種偏序關(guān)系”“求兩個排列之間的相似度”甚至某些推薦排序場景里的亂序程度評估背后都是同一套分治計數(shù)思想。每次遇到新的“成對計數(shù)”問題我都會先問一句能不能在排序的過程中順便統(tǒng)計如果能那大概率就是歸并排序變種。6.1 從逆序?qū)Φ狡驅(qū)栴}的想象力如果把“逆序?qū)Α钡呐卸l件從nums[i] nums[j]換成其他比較規(guī)則比如nums[i] 2 * nums[j]或者附帶一些額外結(jié)構(gòu)體字段比較算法框架仍然成立。真正需要修改的只是合并時的判斷條件和計數(shù)公式。理解到這一層題目就不再是背模板而是變成一種“排序時批量處理相對關(guān)系”的思維工具。6.2 我檢查這類代碼的經(jīng)驗我現(xiàn)在寫這類函數(shù)一定會先跑三件事用空數(shù)組、長度為 1 的數(shù)組驗證越界問題用完全升序和完全降序的數(shù)組驗證計數(shù)的上下邊界用包含重復(fù)元素的數(shù)組驗證等號條件。這三個都過了再拿暴力版做隨機(jī)交叉驗證。很多邊界問題比如 Go 切片索引、遞歸終止條件、計數(shù)溢出都能在這一套流程里暴露出來。這套流程看起來很簡單但能在很長時間里幫我少走彎路。