1. 逆序?qū)Φ亩x為什么這一題能攔住很多人我第一次認真接觸“逆序?qū)Α笔窃谔幚硪慌判蚪y(tǒng)計相關(guān)的小工具時。當時我需要量化一組序列到底“有多亂”排序本身只能給出結(jié)果順序卻丟失了原始亂序程度。后來才意識到逆序?qū)?shù)量正好是一個可以精確描述亂序程度的指標對于一個數(shù)組nums只要下標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)。面試里也經(jīng)常問這道題它的本意不是考察你會不會枚舉所有數(shù)對而是考察你能不能把統(tǒng)計過程融進排序過程里做到 O(n log n) 的時間復(fù)雜度。1.1 一個例子把定義說清楚拿[3, 1, 2]來舉例。數(shù)組下標從 0 開始三個元素能組成三對下標(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é)上可以直接反映亂序程度但它又不是一個線性指標。升序數(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當數(shù)組長度為 100000 時理論最大值已經(jīng)接近 50 億普通 32 位整數(shù)很可能裝不下。從第一版代碼就使用 64 位整數(shù)可以少踩一個非常隱蔽的坑。2.2 規(guī)模大了以后會發(fā)生什么暴力解法的時間復(fù)雜度是 O(n^2)。假設(shè)一臺機器每秒能執(zhí)行大約一億次基本比較當數(shù)組長度來到 10000大約需要執(zhí)行 5000 萬次比較肉眼可能還能接受當長度來到 100000需要執(zhí)行 50 億次比較運行時間會從毫秒級直接跨到秒級甚至更久再往上到 1000000那就是災(zāi)難。我在實際測試時用隨機數(shù)組跑過兩個版本的對比。長度 1 萬以內(nèi)暴力版和歸并版幾乎看不出差距長度 10 萬時暴力版已經(jīng)明顯卡頓而歸并版仍然在個位數(shù)毫秒級別。這里想說的并不是暴力版“一無是處”相反它非常適合做基準驗證我先用暴力版算出正確答案再拿歸并版去對照能快速確定優(yōu)化版本有沒有寫錯。我到現(xiàn)在都習(xí)慣把暴力版留在測試代碼里作為交叉驗證的基準。還有一個容易被忽略的點暴力版會真實地枚舉所有數(shù)對所以它對任何規(guī)模的數(shù)據(jù)都能給出確定結(jié)果不存在遞歸深度、邊界處理之類的問題。因此在小數(shù)組的單元測試中用暴力版做標準答案是非常穩(wěn)妥的策略。3. 歸并排序解法把計數(shù)融進排序過程的三個關(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ū)Α＿f歸能解決前兩部分合并時只需要重點處理第三部分。這個“分治”視角和暴力枚舉完全不同暴力枚舉把每一對都看作獨立個體而歸并解法把大量比較壓縮到了合并階段。因此整個算法的時間復(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分別指向當前左右元素誰小先放入臨時數(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”因為當前這一步取了右邊的arr[j]說明右邊的這個元素小于左邊當前指針指向的元素?？勺筮呏羔樅竺娴脑馗笏鼈冏匀灰捕即笥谶@個右邊的元素。這幾個逆序?qū)υ谶@一步被批量統(tǒng)計了等指針再往后走這些元素就再也不會和同一個右邊的arr[j]組成任何新對因此不會漏計也不會重復(fù)計。等號的處理也要特別留意如果arr[i] arr[j]說明左邊元素不大于右邊元素此時不構(gòu)成逆序?qū)?。如果誤寫成會把相等的兩個元素也當成逆序?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)在進入最后的合并左邊是[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)存分配機制和 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í)慣也能避免邊界計算中的細小問題。第三個設(shè)計點是遞歸邊界left right。這個條件看似簡單卻在數(shù)組為空時特別關(guān)鍵。當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)。但實際運行時的常數(shù)開銷比我想象中要小不少因為切片拷貝使用 Go 底層的內(nèi)存復(fù)制合并過程是線性掃描沒有額外復(fù)雜操作。我在測試數(shù)據(jù)規(guī)模 100 萬亂序整數(shù)時單次調(diào)用大約在幾百毫秒級別具體取決于機器。這個規(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) } }) } }固定用例之外更重要的是隨機交叉驗證。我會生成長度從 0 到 50 的隨機數(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) } } } }這個隨機測試里我還順帶校驗了一件事調(diào)用完InversePairs后原數(shù)組沒有被排序過程改掉。因為我先拷貝了輸入所以這個檢查一定通過如果實現(xiàn)里直接拿外部切片排序這個測試就會立刻報警。5.2 重復(fù)元素導(dǎo)致的最大坑相等到底算不算很多人的第一版實現(xiàn)會把arr[i] arr[j]寫成arr[i] arr[j]導(dǎo)致相等的兩個元素被當成逆序?qū)?。比如[2, 2]規(guī)范答案是 0因為2并不大于2但如果比較條件寫錯會統(tǒng)計成 1。這個問題在包含大量重復(fù)值的業(yè)務(wù)數(shù)據(jù)中非常致命。我一開始也踩過這個坑測試數(shù)據(jù)全是隨機整數(shù)很少在意重復(fù)值是否統(tǒng)計正確。后來加了一組包含大量重復(fù)元素的壓測用例才暴露出來。所以我在固定用例里特意寫了{重復(fù)元素, []int{2, 2, 1, 1}, 4}就是要保證相等元素不會被誤計。5.3 別改動入?yún)⒊悄阌忻鞔_理由歸并排序天然會改變原數(shù)組順序。在純粹刷題場景里改掉傳入數(shù)組可能無所謂但在工程項目中調(diào)用方往往還持有這份數(shù)據(jù)做后續(xù)計算一旦被排序后續(xù)邏輯全亂。我建議的默認做法是在入口處拷貝一次輸入。雖然多出 O(n) 的拷貝時間但能換來非?？少F的確定性。上面的源碼也是這么做的。如果對性能極其敏感可以在文檔里明確標注“此函數(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ù)組驗證等號條件。這三個都過了再拿暴力版做隨機交叉驗證。很多邊界問題比如 Go 切片索引、遞歸終止條件、計數(shù)溢出都能在這一套流程里暴露出來。這套流程看起來很簡單但能在很長時間里幫我少走彎路。