算逆序數(shù)：從原理到實(shí)戰(zhàn)模板解析)
1. 從一道經(jīng)典面試題說(shuō)起為什么“逆序數(shù)”值得深究如果你刷過(guò)一些算法題或者參加過(guò)技術(shù)面試大概率遇到過(guò)“計(jì)算數(shù)組逆序?qū)Α边@個(gè)問(wèn)題。題目描述很簡(jiǎn)單給定一個(gè)整數(shù)數(shù)組統(tǒng)計(jì)其中有多少個(gè)逆序?qū)?。所謂逆序?qū)褪侵冈跀?shù)組中如果下標(biāo)i j但數(shù)值a[i] a[j]那么(a[i], a[j])就構(gòu)成一個(gè)逆序?qū)ΑＵб豢催@似乎是一個(gè)簡(jiǎn)單的雙重循環(huán)就能解決的O(n2)問(wèn)題。然而當(dāng)面試官微笑著告訴你數(shù)組長(zhǎng)度n可能高達(dá)10^5甚至10^6時(shí)你立刻會(huì)明白暴力解法在時(shí)間限制面前不堪一擊。這正是“逆序數(shù)”問(wèn)題的魅力所在它絕不僅僅是一個(gè)簡(jiǎn)單的計(jì)數(shù)問(wèn)題。它像一塊試金石直接檢驗(yàn)?zāi)闶欠窭斫馊绾卫媒?jīng)典算法思想分治、歸并排序來(lái)優(yōu)化時(shí)間復(fù)雜度。在實(shí)際場(chǎng)景中逆序數(shù)的概念也廣泛存在衡量一個(gè)排列的“混亂度”或“距離有序的遠(yuǎn)近”在金融分析中用于評(píng)估序列的波動(dòng)性甚至在推薦系統(tǒng)中分析用戶(hù)偏好序列的差異。今天我們不談空泛的理論就從一個(gè)最樸素的需求出發(fā)——如何高效、優(yōu)雅地計(jì)算一個(gè)數(shù)組的逆序?qū)倲?shù)并把它封裝成一個(gè)可以“拿來(lái)就用”的可靠模板。這個(gè)模板的核心就是歸并排序。2. 歸并排序不只是排序更是分治計(jì)數(shù)的利器要理解如何用歸并排序計(jì)算逆序數(shù)首先得吃透歸并排序本身。很多人對(duì)歸并排序的印象停留在“穩(wěn)定、O(n log n)的排序算法”卻忽略了它在“分治過(guò)程中處理跨區(qū)間關(guān)系”這一獨(dú)特優(yōu)勢(shì)。2.1 歸并排序的核心思想再回顧歸并排序采用典型的分治策略分解將當(dāng)前待排序的數(shù)組遞歸地分成兩半直到每個(gè)子數(shù)組只剩下一個(gè)元素自然有序。解決遞歸地對(duì)左右兩個(gè)子數(shù)組進(jìn)行排序。合并將兩個(gè)已經(jīng)有序的子數(shù)組合并成一個(gè)新的有序數(shù)組。這是整個(gè)算法的關(guān)鍵步驟。合并過(guò)程通常使用雙指針。假設(shè)我們有兩個(gè)已排序的子數(shù)組left和right以及一個(gè)臨時(shí)數(shù)組temp。我們用指針i和j分別指向left和right的起始位置比較left[i]和right[j]將較小的那個(gè)放入temp并移動(dòng)相應(yīng)的指針。2.2 逆序數(shù)產(chǎn)生的契機(jī)就在“合并”這一步計(jì)算逆序數(shù)的智慧就藏在這個(gè)合并邏輯里。我們考慮合并兩個(gè)已經(jīng)各自有序的子數(shù)組時(shí)的情況。假設(shè)左子數(shù)組left為[5, 7, 9]右子數(shù)組right為[4, 6, 8]。它們內(nèi)部已經(jīng)沒(méi)有逆序?qū)α艘驗(yàn)楦髯杂行?。但是跨左右兩個(gè)子數(shù)組的逆序?qū)π枰诤喜r(shí)被識(shí)別和計(jì)數(shù)。合并開(kāi)始比較left[0]5和right[0]4。因?yàn)? 4根據(jù)逆序?qū)Χxi j且a[i] a[j]在原始數(shù)組中5來(lái)自左半部分的下標(biāo)肯定小于4來(lái)自右半部分的下標(biāo)但值卻更大。因此(5, 4)構(gòu)成一個(gè)逆序?qū)?。關(guān)鍵推論由于左子數(shù)組left是有序的如果left[i] right[j]那么left[i]以及l(fā)eft數(shù)組中i之后的所有元素left[i1],left[i2], ...都必然大于right[j]。因?yàn)閿?shù)組是升序的后面的元素只會(huì)更大。所以當(dāng)我們將right[j]放入臨時(shí)數(shù)組時(shí)它不僅僅與left[i]構(gòu)成逆序?qū)Χ桥cleft數(shù)組中從i到末尾的所有元素都構(gòu)成逆序?qū)?。這個(gè)數(shù)量是mid - i 1假設(shè)left的區(qū)間是[l, mid]。在上面的例子中當(dāng)5 4時(shí)left中從5開(kāi)始往后的所有元素[5, 7, 9]都大于4。因此元素4貢獻(xiàn)的逆序?qū)?shù)量是3。通過(guò)這種方式在歸并排序的合并過(guò)程中我們可以在O(n)的時(shí)間內(nèi)順帶統(tǒng)計(jì)出所有“跨左右子數(shù)組”的逆序?qū)?shù)量。而遞歸過(guò)程會(huì)確保所有可能的逆序?qū)ν笞訑?shù)組內(nèi)、同右子數(shù)組內(nèi)、跨子數(shù)組都被考慮到。同子數(shù)組內(nèi)的逆序?qū)?huì)在更深層的遞歸中被統(tǒng)計(jì)。3. 逆序數(shù)模板的逐行實(shí)現(xiàn)與解析理解了原理我們來(lái)動(dòng)手實(shí)現(xiàn)這個(gè)模板。我將提供一個(gè)清晰、注釋完整、可直接復(fù)用的 C 版本并逐行解釋其設(shè)計(jì)意圖和細(xì)節(jié)。#include vector using namespace std; typedef long long LL; // 逆序數(shù)可能很大用 long long 防止溢出 // 歸并排序并計(jì)算逆序數(shù) LL mergeSortAndCount(vectorint nums, int left, int right, vectorint temp) { // 遞歸基如果區(qū)間只有一個(gè)或零個(gè)元素逆序?qū)? if (left right) { return 0; } // 1. 分找到中間點(diǎn)將區(qū)間一分為二 int mid left (right - left) / 2; // 防止(leftright)溢出 // 2. 治遞歸計(jì)算左右子區(qū)間的逆序數(shù)并讓子區(qū)間有序 LL inv_count 0; inv_count mergeSortAndCount(nums, left, mid, temp); inv_count mergeSortAndCount(nums, mid 1, right, temp); // 3. 合合并兩個(gè)有序子數(shù)組并計(jì)算跨越中點(diǎn)的逆序數(shù) int i left; // 左子數(shù)組起始指針 int j mid 1; // 右子數(shù)組起始指針 int k left; // 臨時(shí)數(shù)組填充指針 while (i mid j right) { if (nums[i] nums[j]) { // 情況A左元素 右元素不構(gòu)成逆序?qū)?// 將左元素放入臨時(shí)數(shù)組移動(dòng)左指針 temp[k] nums[i]; } else { // 情況B左元素 右元素構(gòu)成逆序?qū)?// 此時(shí)nums[i...mid] 的所有元素都大于 nums[j] inv_count (mid - i 1); // 核心計(jì)數(shù)邏輯 // 將右元素較小的那個(gè)放入臨時(shí)數(shù)組移動(dòng)右指針 temp[k] nums[j]; } } // 4. 收尾將剩余元素拷貝到臨時(shí)數(shù)組 while (i mid) { temp[k] nums[i]; } while (j right) { temp[k] nums[j]; } // 5. 將排序好的臨時(shí)數(shù)組部分拷貝回原數(shù)組 for (int idx left; idx right; idx) { nums[idx] temp[idx]; } return inv_count; } // 對(duì)外接口計(jì)算數(shù)組 nums 的逆序?qū)倲?shù) LL countInversions(vectorint nums) { int n nums.size(); if (n 2) return 0; // 邊界情況處理 vectorint temp(n); // 一次性分配與原始數(shù)組等大的臨時(shí)空間避免遞歸中反復(fù)分配 return mergeSortAndCount(nums, 0, n - 1, temp); }3.1 關(guān)鍵代碼段深度解析1. 遞歸基與中點(diǎn)計(jì)算if (left right) return 0;這是遞歸的終止條件。當(dāng)區(qū)間內(nèi)沒(méi)有或只有一個(gè)元素時(shí)逆序?qū)ψ匀粸?。int mid left (right - left) / 2;這是計(jì)算中點(diǎn)的標(biāo)準(zhǔn)安全寫(xiě)法避免了(left right) / 2在兩者都很大時(shí)可能發(fā)生的整數(shù)溢出。2. 遞歸調(diào)用inv_count mergeSortAndCount(nums, left, mid, temp);inv_count mergeSortAndCount(nums, mid 1, right, temp);這兩行代碼完成了“分”與“治”。它們不僅遞歸地對(duì)左右兩部分進(jìn)行排序更重要的是累加了左右兩部分內(nèi)部的逆序?qū)?shù)量。遞歸會(huì)一直深入到單個(gè)元素。3. 核心合并與計(jì)數(shù)邏輯這是整個(gè)算法的靈魂。if (nums[i] nums[j])注意這里用的是而不是。這是為了保持排序的穩(wěn)定性如果存在相等元素原先在左邊的依然在左邊。在逆序?qū)Χx中嚴(yán)格大于才構(gòu)成逆序所以這里用不會(huì)漏計(jì)也不會(huì)多計(jì)。else分支當(dāng)nums[i] nums[j]時(shí)觸發(fā)。此時(shí)nums[j]這個(gè)來(lái)自右半部分的元素比當(dāng)前左半部分指針i所指元素以及之后的所有元素都小。因此nums[j]與nums[i], nums[i1], ..., nums[mid]都構(gòu)成逆序?qū)?。?shù)量正好是(mid - i 1)。為什么這樣計(jì)數(shù)是正確的因?yàn)榇藭r(shí)左右兩個(gè)子數(shù)組在遞歸后已經(jīng)各自有序。所以nums[i...mid]是左半部分剩余的最小到最大的序列它們都大于nums[j]。這個(gè)關(guān)系是確定的。4. 收尾與拷貝while循環(huán)處理剩余元素。注意只有當(dāng)左半部分有剩余時(shí)這些剩余元素已經(jīng)比所有右半部分已處理的元素都大但它們與右半部分元素的關(guān)系在之前的else分支中已經(jīng)全部計(jì)算過(guò)了所以這里不需要再計(jì)數(shù)?？截惢卦瓟?shù)組是為了讓上一層遞歸合并時(shí)傳入的已經(jīng)是排序好的子數(shù)組。5. 對(duì)外接口與臨時(shí)數(shù)組vectorint temp(n);在入口函數(shù)中一次性分配好臨時(shí)數(shù)組然后在整個(gè)遞歸過(guò)程中復(fù)用。這比在每次遞歸調(diào)用中創(chuàng)建臨時(shí)向量要高效得多避免了頻繁的內(nèi)存分配與釋放。4. 模板的變體、邊界與實(shí)戰(zhàn)調(diào)試一個(gè)可靠的模板不僅要能解決標(biāo)準(zhǔn)問(wèn)題還要能應(yīng)對(duì)各種變體和邊界情況。下面我們探討幾個(gè)常見(jiàn)場(chǎng)景。4.1 處理“元素值很大”或“非整數(shù)”的情況我們的模板直接比較nums[i]和nums[j]。如果數(shù)組元素是浮點(diǎn)數(shù)或者范圍極大的整數(shù)模板本身無(wú)需修改。但如果問(wèn)題場(chǎng)景發(fā)生變化呢場(chǎng)景一需要計(jì)算基于索引的特定逆序?qū)Α＠珙}目要求i j且nums[i] 2 * nums[j]。這時(shí)核心比較邏輯變了我們不能在合并時(shí)直接利用有序性。一種常見(jiàn)技巧是在合并之前先用一個(gè)循環(huán)遍歷左右子數(shù)組專(zhuān)門(mén)統(tǒng)計(jì)滿(mǎn)足nums[i] 2 * nums[j]的對(duì)數(shù)因?yàn)榇藭r(shí)左右都已有序可以用雙指針以 O(n) 完成然后再進(jìn)行正常的合并排序。這相當(dāng)于在歸并排序的框架內(nèi)嵌入了一段額外的統(tǒng)計(jì)邏輯。場(chǎng)景二數(shù)組元素是自定義對(duì)象。這時(shí)我們需要定義好對(duì)象的比較規(guī)則重載或運(yùn)算符或者修改模板中的比較部分使其能夠處理自定義類(lèi)型。模板的歸并框架依然適用。4.2 調(diào)試與驗(yàn)證如何確保你的模板是對(duì)的當(dāng)你寫(xiě)出模板后如何驗(yàn)證其正確性我推薦一個(gè)“暴力對(duì)拍”的方法這對(duì)于算法競(jìng)賽和面試準(zhǔn)備極其有用。編寫(xiě)暴力算法寫(xiě)一個(gè) O(n2) 的雙重循環(huán)函數(shù)bruteForceCount用于計(jì)算小規(guī)模數(shù)據(jù)例如 n 1000的逆序數(shù)。隨機(jī)數(shù)據(jù)生成器寫(xiě)一個(gè)函數(shù)生成隨機(jī)長(zhǎng)度、隨機(jī)內(nèi)容的數(shù)組。自動(dòng)化對(duì)比在循環(huán)中生成隨機(jī)數(shù)組分別用你的歸并模板和暴力算法計(jì)算逆序數(shù)比較結(jié)果是否一致。運(yùn)行成千上萬(wàn)次隨機(jī)測(cè)試。邊界測(cè)試空數(shù)組。單元素?cái)?shù)組。完全升序的數(shù)組逆序數(shù)為0。完全降序的數(shù)組逆序數(shù)為n*(n-1)/2。所有元素都相同的數(shù)組逆序數(shù)為0。通過(guò)這種大規(guī)模的隨機(jī)測(cè)試你可以對(duì)模板的正確性建立起極強(qiáng)的信心。這也是在實(shí)際工程中驗(yàn)證復(fù)雜算法邏輯的常用手段。4.3 一個(gè)容易忽略的細(xì)節(jié)逆序數(shù)總數(shù)的數(shù)據(jù)類(lèi)型注意看我們的模板逆序數(shù)總數(shù)inv_count和函數(shù)返回值用的是long long (LL)。這是非常關(guān)鍵的一點(diǎn)。對(duì)于一個(gè)長(zhǎng)度為n的數(shù)組逆序?qū)Φ淖畲髷?shù)量發(fā)生在數(shù)組完全逆序時(shí)數(shù)量是n*(n-1)/2。當(dāng)n 10^5時(shí)這個(gè)值大約是5 * 10^9已經(jīng)超過(guò)了 32 位 int 的最大值約2.1 * 10^9。如果用int存儲(chǔ)會(huì)導(dǎo)致溢出得到錯(cuò)誤的結(jié)果。因此在涉及可能的大數(shù)計(jì)數(shù)時(shí)養(yǎng)成使用long long的習(xí)慣這是一個(gè)老手才會(huì)特別注意的坑。5. 從模板到應(yīng)用解決 LeetCode 經(jīng)典例題理論說(shuō)得再多不如實(shí)戰(zhàn)一場(chǎng)。我們直接用這個(gè)模板去解決 LeetCode 上的兩道經(jīng)典題目看看如何微調(diào)模板以適應(yīng)具體問(wèn)題。5.1 LeetCode 493. 翻轉(zhuǎn)對(duì)這是逆序數(shù)問(wèn)題的一個(gè)著名變體。題目要求給定一個(gè)數(shù)組nums返回翻轉(zhuǎn)對(duì)的數(shù)量。翻轉(zhuǎn)對(duì)定義為滿(mǎn)足以下條件的下標(biāo)對(duì)(i, j)i jnums[i] 2 * nums[j]分析這和標(biāo)準(zhǔn)逆序?qū)ums[i] nums[j]很像但比較條件變成了 2 *。關(guān)鍵在于在歸并排序的合并過(guò)程中左右子數(shù)組是有序的但nums[i] 2 * nums[j]這個(gè)條件并不能像nums[i] nums[j]那樣在比較合并元素時(shí)順帶高效計(jì)算。因?yàn)榧词筺ums[i] nums[j]也可能有nums[i] 2 * nums[j]例如nums[i]3, nums[j]1。解決方案我們需要在合并兩個(gè)有序子數(shù)組之前單獨(dú)進(jìn)行一次遍歷來(lái)統(tǒng)計(jì)“翻轉(zhuǎn)對(duì)”。由于左右子數(shù)組已經(jīng)有序我們可以用雙指針 O(n) 地完成這次統(tǒng)計(jì)然后再進(jìn)行正常的合并操作。代碼調(diào)整示例 在mergeSortAndCount函數(shù)的遞歸調(diào)用之后、合并操作之前插入一段統(tǒng)計(jì)代碼// ... 遞歸調(diào)用之后 ... // 統(tǒng)計(jì)當(dāng)前左右子數(shù)組之間的“翻轉(zhuǎn)對(duì)” int p left, q mid 1; while (p mid q right) { if ((long long)nums[p] 2 * (long long)nums[q]) { // 注意類(lèi)型轉(zhuǎn)換防止溢出 inv_count (mid - p 1); q; } else { p; } } // ... 后續(xù)進(jìn)行正常的合并操作 ...注意這里(long long)轉(zhuǎn)換至關(guān)重要因?yàn)閚ums[i] * 2可能導(dǎo)致 32 位 int 溢出。5.2 LeetCode 315. 計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)這是逆序數(shù)問(wèn)題的另一個(gè)經(jīng)典變體也是面試高頻題。題目要求返回一個(gè)新的數(shù)組counts其中counts[i]的值是nums[i]右側(cè)小于nums[i]的元素的數(shù)量。分析這本質(zhì)上就是求“以每個(gè)元素為左元素的逆序?qū)Α睌?shù)量。標(biāo)準(zhǔn)逆序數(shù)模板求得是總數(shù)。我們需要為每個(gè)元素單獨(dú)計(jì)數(shù)。思路是在歸并排序的過(guò)程中元素的位置會(huì)發(fā)生變化我們需要一種方法在元素移動(dòng)時(shí)還能知道它是誰(shuí)并更新它的計(jì)數(shù)。解決方案使用“索引數(shù)組”。我們不對(duì)原始值數(shù)組nums進(jìn)行排序而是對(duì)一個(gè)索引數(shù)組indexes進(jìn)行排序。排序的比較規(guī)則是基于nums[indexes[i]]的值。在合并過(guò)程中當(dāng)我們將一個(gè)右半部分的索引對(duì)應(yīng)原數(shù)組某個(gè)元素放入臨時(shí)數(shù)組時(shí)意味著這個(gè)右半部分的元素比當(dāng)前左半部分剩余的所有元素都“小”在排序意義上。那么這些左半部分剩余元素對(duì)應(yīng)的原數(shù)組位置其“右側(cè)小于它的數(shù)量”就應(yīng)該增加 1。但注意右半部分的元素在原數(shù)組中確實(shí)是在左側(cè)元素的右邊。實(shí)現(xiàn)要點(diǎn)創(chuàng)建vectorint indexes(n)初始為[0, 1, 2, ..., n-1]。vectorint count(n, 0)記錄結(jié)果。歸并排序的對(duì)象是indexes數(shù)組。比較時(shí)用nums[indexes[i]]。在合并的else分支即nums[indexes[i]] nums[indexes[j]]時(shí)我們需要更新計(jì)數(shù)。但這里更新的不是indexes[j]而是左半部分所有剩余元素對(duì)應(yīng)的計(jì)數(shù)。因?yàn)閕ndexes[j]來(lái)自右半部分它小于左半部分當(dāng)前及之后的所有元素所以這些左半部分的元素其“右側(cè)小元素”數(shù)量都應(yīng)該 1。更高效的做法是在將右半部分元素放入臨時(shí)數(shù)組時(shí)用一個(gè)變量記錄本次從右半部分取出了多少個(gè)元素記為right_count在后續(xù)將左半部分元素放入臨時(shí)數(shù)組時(shí)將其計(jì)數(shù)增加right_count。但更清晰的做法是在else分支中直接遍歷左半部分剩余元素增加計(jì)數(shù)。為了效率我們通常采用一個(gè)“計(jì)數(shù)器”累加的方式。這道題的實(shí)現(xiàn)細(xì)節(jié)比標(biāo)準(zhǔn)模板復(fù)雜但它完美體現(xiàn)了歸并排序分治思想在解決“帶位置信息計(jì)數(shù)”問(wèn)題上的強(qiáng)大能力。通過(guò)練習(xí)這道題你對(duì)逆序數(shù)模板的理解會(huì)從“求和”深入到“分配”的層面。6. 性能分析與橫向?qū)Ρ葹槭裁词菤w并排序我們已經(jīng)實(shí)現(xiàn)了模板也看到了它的應(yīng)用?，F(xiàn)在我們來(lái)深入分析一下為什么歸并排序是解決逆序數(shù)問(wèn)題的“天選之子”以及其他方法為什么不行。6.1 時(shí)間復(fù)雜度O(n log n) 的必然性歸并排序的時(shí)間復(fù)雜度是 O(n log n)這是基于比較的排序算法的下限。計(jì)算逆序數(shù)本質(zhì)上是一個(gè)基于比較的計(jì)數(shù)問(wèn)題它至少需要讀取所有數(shù)據(jù)其時(shí)間復(fù)雜度下限也是 O(n log n)可以通過(guò)決策樹(shù)模型證明。因此歸并排序方案是漸進(jìn)最優(yōu)的。暴力法 O(n2)數(shù)據(jù)量稍大如 n10^5就完全不可行。樹(shù)狀數(shù)組/二叉索引樹(shù) (Fenwick Tree) O(n log n)這也是一個(gè)非常優(yōu)秀的解法。其思路是離散化數(shù)組值后從右向左遍歷查詢(xún)當(dāng)前值之前有多少個(gè)小于它的數(shù)即前綴和然后更新樹(shù)狀數(shù)組。它的復(fù)雜度也是 O(n log n)且常數(shù)很小。與歸并排序相比它需要額外的離散化步驟和 O(n) 的空間。兩種方法在時(shí)間復(fù)雜度上打平歸并排序的優(yōu)勢(shì)在于其思路與排序過(guò)程天然結(jié)合更直觀體現(xiàn)分治思想。線段樹(shù)同樣可以解決但代碼量通常比樹(shù)狀數(shù)組和歸并排序都要大在此問(wèn)題上不是最簡(jiǎn)潔的選擇。6.2 空間復(fù)雜度O(n) 的權(quán)衡歸并排序需要 O(n) 的額外空間臨時(shí)數(shù)組temp。這是一個(gè)典型的“以空間換時(shí)間”的策略。在絕大多數(shù)算法競(jìng)賽和面試場(chǎng)景中空間限制通常是寬松的如 256MB 或 512MBO(n) 的空間消耗對(duì)于 n 高達(dá) 10^6 是完全可以接受的。樹(shù)狀數(shù)組解法也需要 O(n) 的空間用于存儲(chǔ)樹(shù)狀結(jié)構(gòu)。因此在空間復(fù)雜度上兩者也是打平的。6.3 穩(wěn)定性與可擴(kuò)展性歸并排序是穩(wěn)定的排序算法。這在某些變體問(wèn)題中很重要例如當(dāng)數(shù)組元素相同時(shí)穩(wěn)定的排序能保證我們不會(huì)多算或少算逆序?qū)Ω鶕?jù)問(wèn)題定義相等通常不構(gòu)成逆序。樹(shù)狀數(shù)組解法本身與排序穩(wěn)定性無(wú)關(guān)。在可擴(kuò)展性方面歸并排序的框架更容易嵌入其他復(fù)雜的統(tǒng)計(jì)邏輯正如我們?cè)?LeetCode 493 題中做的那樣——在合并前增加一個(gè)統(tǒng)計(jì)步驟。這種“分治-統(tǒng)計(jì)-合并”的模式非常清晰。而樹(shù)狀數(shù)組更擅長(zhǎng)處理動(dòng)態(tài)的前綴和查詢(xún)與更新對(duì)于復(fù)雜的跨區(qū)間統(tǒng)計(jì)有時(shí)不如歸并排序框架直觀。7. 模板的終極記憶法與編碼肌肉記憶最后我們來(lái)談?wù)勅绾握嬲莆者@個(gè)模板達(dá)到在面試或競(jìng)賽中能快速、準(zhǔn)確寫(xiě)出來(lái)的程度。死記硬背是不可靠的理解基礎(chǔ)上的“肌肉記憶”才是關(guān)鍵。記憶要點(diǎn)拆解函數(shù)簽名LL mergeSortAndCount(vectorint nums, int left, int right, vectorint temp)。記住需要原數(shù)組、左右邊界、臨時(shí)數(shù)組。遞歸基if (left right) return 0;計(jì)算中點(diǎn)int mid left (right - left) / 2;遞歸調(diào)用累加左右結(jié)果。合并前初始化指針ileft, jmid1, kleft。核心 while 循環(huán)if (nums[i] nums[j]): 放nums[i]i。else:累加逆序數(shù)inv_count (mid - i 1)放nums[j]j。收尾循環(huán)把剩下的i或j部分拷貝完。拷貝回原數(shù)組for (idx from left to right) nums[idx] temp[idx]。返回總逆序數(shù)。編碼練習(xí)建議白板練習(xí)在紙上或白板上不參考任何資料從零開(kāi)始默寫(xiě)整個(gè)函數(shù)。寫(xiě)完后對(duì)照檢查。閉眼模擬在腦子里模擬一個(gè)簡(jiǎn)單數(shù)組如[3, 1, 2]的整個(gè)遞歸、合并、計(jì)數(shù)過(guò)程。想象調(diào)用棧、指針移動(dòng)和inv_count的變化。變體挑戰(zhàn)嘗試修改模板去解決 LeetCode 315 或 493。即使一開(kāi)始寫(xiě)不出來(lái)思考的過(guò)程也能極大加深理解。定時(shí)訓(xùn)練設(shè)定 5-7 分鐘目標(biāo)是能一次性無(wú)錯(cuò)寫(xiě)出標(biāo)準(zhǔn)模板。速度和質(zhì)量并重。當(dāng)你經(jīng)過(guò)多次練習(xí)后你會(huì)發(fā)現(xiàn)這個(gè)模板就像一段旋律一樣刻在腦子里。它的核心邏輯——在合并有序序列時(shí)利用有序性批量計(jì)數(shù)跨區(qū)間逆序?qū)Α獙⒊蔀槟憬鉀Q一系列分治計(jì)數(shù)問(wèn)題的強(qiáng)大思維工具。這遠(yuǎn)遠(yuǎn)超越了一道題本身而是掌握了一種重要的算法范式。 歸并排序高效計(jì)算逆序數(shù)：從原理到實(shí)戰(zhàn)模板解析
1. 從一道經(jīng)典面試題說(shuō)起為什么“逆序數(shù)”值得深究如果你刷過(guò)一些算法題或者參加過(guò)技術(shù)面試大概率遇到過(guò)“計(jì)算數(shù)組逆序?qū)Α边@個(gè)問(wèn)題。題目描述很簡(jiǎn)單給定一個(gè)整數(shù)數(shù)組統(tǒng)計(jì)其中有多少個(gè)逆序?qū)?。所謂逆序?qū)褪侵冈跀?shù)組中如果下標(biāo)i j但數(shù)值a[i] a[j]那么(a[i], a[j])就構(gòu)成一個(gè)逆序?qū)ΑＵб豢催@似乎是一個(gè)簡(jiǎn)單的雙重循環(huán)就能解決的O(n2)問(wèn)題。然而當(dāng)面試官微笑著告訴你數(shù)組長(zhǎng)度n可能高達(dá)10^5甚至10^6時(shí)你立刻會(huì)明白暴力解法在時(shí)間限制面前不堪一擊。這正是“逆序數(shù)”問(wèn)題的魅力所在它絕不僅僅是一個(gè)簡(jiǎn)單的計(jì)數(shù)問(wèn)題。它像一塊試金石直接檢驗(yàn)?zāi)闶欠窭斫馊绾卫媒?jīng)典算法思想分治、歸并排序來(lái)優(yōu)化時(shí)間復(fù)雜度。在實(shí)際場(chǎng)景中逆序數(shù)的概念也廣泛存在衡量一個(gè)排列的“混亂度”或“距離有序的遠(yuǎn)近”在金融分析中用于評(píng)估序列的波動(dòng)性甚至在推薦系統(tǒng)中分析用戶(hù)偏好序列的差異。今天我們不談空泛的理論就從一個(gè)最樸素的需求出發(fā)——如何高效、優(yōu)雅地計(jì)算一個(gè)數(shù)組的逆序?qū)倲?shù)并把它封裝成一個(gè)可以“拿來(lái)就用”的可靠模板。這個(gè)模板的核心就是歸并排序。2. 歸并排序不只是排序更是分治計(jì)數(shù)的利器要理解如何用歸并排序計(jì)算逆序數(shù)首先得吃透歸并排序本身。很多人對(duì)歸并排序的印象停留在“穩(wěn)定、O(n log n)的排序算法”卻忽略了它在“分治過(guò)程中處理跨區(qū)間關(guān)系”這一獨(dú)特優(yōu)勢(shì)。2.1 歸并排序的核心思想再回顧歸并排序采用典型的分治策略分解將當(dāng)前待排序的數(shù)組遞歸地分成兩半直到每個(gè)子數(shù)組只剩下一個(gè)元素自然有序。解決遞歸地對(duì)左右兩個(gè)子數(shù)組進(jìn)行排序。合并將兩個(gè)已經(jīng)有序的子數(shù)組合并成一個(gè)新的有序數(shù)組。這是整個(gè)算法的關(guān)鍵步驟。合并過(guò)程通常使用雙指針。假設(shè)我們有兩個(gè)已排序的子數(shù)組left和right以及一個(gè)臨時(shí)數(shù)組temp。我們用指針i和j分別指向left和right的起始位置比較left[i]和right[j]將較小的那個(gè)放入temp并移動(dòng)相應(yīng)的指針。2.2 逆序數(shù)產(chǎn)生的契機(jī)就在“合并”這一步計(jì)算逆序數(shù)的智慧就藏在這個(gè)合并邏輯里。我們考慮合并兩個(gè)已經(jīng)各自有序的子數(shù)組時(shí)的情況。假設(shè)左子數(shù)組left為[5, 7, 9]右子數(shù)組right為[4, 6, 8]。它們內(nèi)部已經(jīng)沒(méi)有逆序?qū)α艘驗(yàn)楦髯杂行?。但是跨左右兩個(gè)子數(shù)組的逆序?qū)π枰诤喜r(shí)被識(shí)別和計(jì)數(shù)。合并開(kāi)始比較left[0]5和right[0]4。因?yàn)? 4根據(jù)逆序?qū)Χxi j且a[i] a[j]在原始數(shù)組中5來(lái)自左半部分的下標(biāo)肯定小于4來(lái)自右半部分的下標(biāo)但值卻更大。因此(5, 4)構(gòu)成一個(gè)逆序?qū)?。關(guān)鍵推論由于左子數(shù)組left是有序的如果left[i] right[j]那么left[i]以及l(fā)eft數(shù)組中i之后的所有元素left[i1],left[i2], ...都必然大于right[j]。因?yàn)閿?shù)組是升序的后面的元素只會(huì)更大。所以當(dāng)我們將right[j]放入臨時(shí)數(shù)組時(shí)它不僅僅與left[i]構(gòu)成逆序?qū)Χ桥cleft數(shù)組中從i到末尾的所有元素都構(gòu)成逆序?qū)?。這個(gè)數(shù)量是mid - i 1假設(shè)left的區(qū)間是[l, mid]。在上面的例子中當(dāng)5 4時(shí)left中從5開(kāi)始往后的所有元素[5, 7, 9]都大于4。因此元素4貢獻(xiàn)的逆序?qū)?shù)量是3。通過(guò)這種方式在歸并排序的合并過(guò)程中我們可以在O(n)的時(shí)間內(nèi)順帶統(tǒng)計(jì)出所有“跨左右子數(shù)組”的逆序?qū)?shù)量。而遞歸過(guò)程會(huì)確保所有可能的逆序?qū)ν笞訑?shù)組內(nèi)、同右子數(shù)組內(nèi)、跨子數(shù)組都被考慮到。同子數(shù)組內(nèi)的逆序?qū)?huì)在更深層的遞歸中被統(tǒng)計(jì)。3. 逆序數(shù)模板的逐行實(shí)現(xiàn)與解析理解了原理我們來(lái)動(dòng)手實(shí)現(xiàn)這個(gè)模板。我將提供一個(gè)清晰、注釋完整、可直接復(fù)用的 C 版本并逐行解釋其設(shè)計(jì)意圖和細(xì)節(jié)。#include vector using namespace std; typedef long long LL; // 逆序數(shù)可能很大用 long long 防止溢出 // 歸并排序并計(jì)算逆序數(shù) LL mergeSortAndCount(vectorint nums, int left, int right, vectorint temp) { // 遞歸基如果區(qū)間只有一個(gè)或零個(gè)元素逆序?qū)? if (left right) { return 0; } // 1. 分找到中間點(diǎn)將區(qū)間一分為二 int mid left (right - left) / 2; // 防止(leftright)溢出 // 2. 治遞歸計(jì)算左右子區(qū)間的逆序數(shù)并讓子區(qū)間有序 LL inv_count 0; inv_count mergeSortAndCount(nums, left, mid, temp); inv_count mergeSortAndCount(nums, mid 1, right, temp); // 3. 合合并兩個(gè)有序子數(shù)組并計(jì)算跨越中點(diǎn)的逆序數(shù) int i left; // 左子數(shù)組起始指針 int j mid 1; // 右子數(shù)組起始指針 int k left; // 臨時(shí)數(shù)組填充指針 while (i mid j right) { if (nums[i] nums[j]) { // 情況A左元素 右元素不構(gòu)成逆序?qū)?// 將左元素放入臨時(shí)數(shù)組移動(dòng)左指針 temp[k] nums[i]; } else { // 情況B左元素 右元素構(gòu)成逆序?qū)?// 此時(shí)nums[i...mid] 的所有元素都大于 nums[j] inv_count (mid - i 1); // 核心計(jì)數(shù)邏輯 // 將右元素較小的那個(gè)放入臨時(shí)數(shù)組移動(dòng)右指針 temp[k] nums[j]; } } // 4. 收尾將剩余元素拷貝到臨時(shí)數(shù)組 while (i mid) { temp[k] nums[i]; } while (j right) { temp[k] nums[j]; } // 5. 將排序好的臨時(shí)數(shù)組部分拷貝回原數(shù)組 for (int idx left; idx right; idx) { nums[idx] temp[idx]; } return inv_count; } // 對(duì)外接口計(jì)算數(shù)組 nums 的逆序?qū)倲?shù) LL countInversions(vectorint nums) { int n nums.size(); if (n 2) return 0; // 邊界情況處理 vectorint temp(n); // 一次性分配與原始數(shù)組等大的臨時(shí)空間避免遞歸中反復(fù)分配 return mergeSortAndCount(nums, 0, n - 1, temp); }3.1 關(guān)鍵代碼段深度解析1. 遞歸基與中點(diǎn)計(jì)算if (left right) return 0;這是遞歸的終止條件。當(dāng)區(qū)間內(nèi)沒(méi)有或只有一個(gè)元素時(shí)逆序?qū)ψ匀粸?。int mid left (right - left) / 2;這是計(jì)算中點(diǎn)的標(biāo)準(zhǔn)安全寫(xiě)法避免了(left right) / 2在兩者都很大時(shí)可能發(fā)生的整數(shù)溢出。2. 遞歸調(diào)用inv_count mergeSortAndCount(nums, left, mid, temp);inv_count mergeSortAndCount(nums, mid 1, right, temp);這兩行代碼完成了“分”與“治”。它們不僅遞歸地對(duì)左右兩部分進(jìn)行排序更重要的是累加了左右兩部分內(nèi)部的逆序?qū)?shù)量。遞歸會(huì)一直深入到單個(gè)元素。3. 核心合并與計(jì)數(shù)邏輯這是整個(gè)算法的靈魂。if (nums[i] nums[j])注意這里用的是而不是。這是為了保持排序的穩(wěn)定性如果存在相等元素原先在左邊的依然在左邊。在逆序?qū)Χx中嚴(yán)格大于才構(gòu)成逆序所以這里用不會(huì)漏計(jì)也不會(huì)多計(jì)。else分支當(dāng)nums[i] nums[j]時(shí)觸發(fā)。此時(shí)nums[j]這個(gè)來(lái)自右半部分的元素比當(dāng)前左半部分指針i所指元素以及之后的所有元素都小。因此nums[j]與nums[i], nums[i1], ..., nums[mid]都構(gòu)成逆序?qū)?。?shù)量正好是(mid - i 1)。為什么這樣計(jì)數(shù)是正確的因?yàn)榇藭r(shí)左右兩個(gè)子數(shù)組在遞歸后已經(jīng)各自有序。所以nums[i...mid]是左半部分剩余的最小到最大的序列它們都大于nums[j]。這個(gè)關(guān)系是確定的。4. 收尾與拷貝while循環(huán)處理剩余元素。注意只有當(dāng)左半部分有剩余時(shí)這些剩余元素已經(jīng)比所有右半部分已處理的元素都大但它們與右半部分元素的關(guān)系在之前的else分支中已經(jīng)全部計(jì)算過(guò)了所以這里不需要再計(jì)數(shù)?？截惢卦瓟?shù)組是為了讓上一層遞歸合并時(shí)傳入的已經(jīng)是排序好的子數(shù)組。5. 對(duì)外接口與臨時(shí)數(shù)組vectorint temp(n);在入口函數(shù)中一次性分配好臨時(shí)數(shù)組然后在整個(gè)遞歸過(guò)程中復(fù)用。這比在每次遞歸調(diào)用中創(chuàng)建臨時(shí)向量要高效得多避免了頻繁的內(nèi)存分配與釋放。4. 模板的變體、邊界與實(shí)戰(zhàn)調(diào)試一個(gè)可靠的模板不僅要能解決標(biāo)準(zhǔn)問(wèn)題還要能應(yīng)對(duì)各種變體和邊界情況。下面我們探討幾個(gè)常見(jiàn)場(chǎng)景。4.1 處理“元素值很大”或“非整數(shù)”的情況我們的模板直接比較nums[i]和nums[j]。如果數(shù)組元素是浮點(diǎn)數(shù)或者范圍極大的整數(shù)模板本身無(wú)需修改。但如果問(wèn)題場(chǎng)景發(fā)生變化呢場(chǎng)景一需要計(jì)算基于索引的特定逆序?qū)Α＠珙}目要求i j且nums[i] 2 * nums[j]。這時(shí)核心比較邏輯變了我們不能在合并時(shí)直接利用有序性。一種常見(jiàn)技巧是在合并之前先用一個(gè)循環(huán)遍歷左右子數(shù)組專(zhuān)門(mén)統(tǒng)計(jì)滿(mǎn)足nums[i] 2 * nums[j]的對(duì)數(shù)因?yàn)榇藭r(shí)左右都已有序可以用雙指針以 O(n) 完成然后再進(jìn)行正常的合并排序。這相當(dāng)于在歸并排序的框架內(nèi)嵌入了一段額外的統(tǒng)計(jì)邏輯。場(chǎng)景二數(shù)組元素是自定義對(duì)象。這時(shí)我們需要定義好對(duì)象的比較規(guī)則重載或運(yùn)算符或者修改模板中的比較部分使其能夠處理自定義類(lèi)型。模板的歸并框架依然適用。4.2 調(diào)試與驗(yàn)證如何確保你的模板是對(duì)的當(dāng)你寫(xiě)出模板后如何驗(yàn)證其正確性我推薦一個(gè)“暴力對(duì)拍”的方法這對(duì)于算法競(jìng)賽和面試準(zhǔn)備極其有用。編寫(xiě)暴力算法寫(xiě)一個(gè) O(n2) 的雙重循環(huán)函數(shù)bruteForceCount用于計(jì)算小規(guī)模數(shù)據(jù)例如 n 1000的逆序數(shù)。隨機(jī)數(shù)據(jù)生成器寫(xiě)一個(gè)函數(shù)生成隨機(jī)長(zhǎng)度、隨機(jī)內(nèi)容的數(shù)組。自動(dòng)化對(duì)比在循環(huán)中生成隨機(jī)數(shù)組分別用你的歸并模板和暴力算法計(jì)算逆序數(shù)比較結(jié)果是否一致。運(yùn)行成千上萬(wàn)次隨機(jī)測(cè)試。邊界測(cè)試空數(shù)組。單元素?cái)?shù)組。完全升序的數(shù)組逆序數(shù)為0。完全降序的數(shù)組逆序數(shù)為n*(n-1)/2。所有元素都相同的數(shù)組逆序數(shù)為0。通過(guò)這種大規(guī)模的隨機(jī)測(cè)試你可以對(duì)模板的正確性建立起極強(qiáng)的信心。這也是在實(shí)際工程中驗(yàn)證復(fù)雜算法邏輯的常用手段。4.3 一個(gè)容易忽略的細(xì)節(jié)逆序數(shù)總數(shù)的數(shù)據(jù)類(lèi)型注意看我們的模板逆序數(shù)總數(shù)inv_count和函數(shù)返回值用的是long long (LL)。這是非常關(guān)鍵的一點(diǎn)。對(duì)于一個(gè)長(zhǎng)度為n的數(shù)組逆序?qū)Φ淖畲髷?shù)量發(fā)生在數(shù)組完全逆序時(shí)數(shù)量是n*(n-1)/2。當(dāng)n 10^5時(shí)這個(gè)值大約是5 * 10^9已經(jīng)超過(guò)了 32 位 int 的最大值約2.1 * 10^9。如果用int存儲(chǔ)會(huì)導(dǎo)致溢出得到錯(cuò)誤的結(jié)果。因此在涉及可能的大數(shù)計(jì)數(shù)時(shí)養(yǎng)成使用long long的習(xí)慣這是一個(gè)老手才會(huì)特別注意的坑。5. 從模板到應(yīng)用解決 LeetCode 經(jīng)典例題理論說(shuō)得再多不如實(shí)戰(zhàn)一場(chǎng)。我們直接用這個(gè)模板去解決 LeetCode 上的兩道經(jīng)典題目看看如何微調(diào)模板以適應(yīng)具體問(wèn)題。5.1 LeetCode 493. 翻轉(zhuǎn)對(duì)這是逆序數(shù)問(wèn)題的一個(gè)著名變體。題目要求給定一個(gè)數(shù)組nums返回翻轉(zhuǎn)對(duì)的數(shù)量。翻轉(zhuǎn)對(duì)定義為滿(mǎn)足以下條件的下標(biāo)對(duì)(i, j)i jnums[i] 2 * nums[j]分析這和標(biāo)準(zhǔn)逆序?qū)ums[i] nums[j]很像但比較條件變成了 2 *。關(guān)鍵在于在歸并排序的合并過(guò)程中左右子數(shù)組是有序的但nums[i] 2 * nums[j]這個(gè)條件并不能像nums[i] nums[j]那樣在比較合并元素時(shí)順帶高效計(jì)算。因?yàn)榧词筺ums[i] nums[j]也可能有nums[i] 2 * nums[j]例如nums[i]3, nums[j]1。解決方案我們需要在合并兩個(gè)有序子數(shù)組之前單獨(dú)進(jìn)行一次遍歷來(lái)統(tǒng)計(jì)“翻轉(zhuǎn)對(duì)”。由于左右子數(shù)組已經(jīng)有序我們可以用雙指針 O(n) 地完成這次統(tǒng)計(jì)然后再進(jìn)行正常的合并操作。代碼調(diào)整示例 在mergeSortAndCount函數(shù)的遞歸調(diào)用之后、合并操作之前插入一段統(tǒng)計(jì)代碼// ... 遞歸調(diào)用之后 ... // 統(tǒng)計(jì)當(dāng)前左右子數(shù)組之間的“翻轉(zhuǎn)對(duì)” int p left, q mid 1; while (p mid q right) { if ((long long)nums[p] 2 * (long long)nums[q]) { // 注意類(lèi)型轉(zhuǎn)換防止溢出 inv_count (mid - p 1); q; } else { p; } } // ... 后續(xù)進(jìn)行正常的合并操作 ...注意這里(long long)轉(zhuǎn)換至關(guān)重要因?yàn)閚ums[i] * 2可能導(dǎo)致 32 位 int 溢出。5.2 LeetCode 315. 計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)這是逆序數(shù)問(wèn)題的另一個(gè)經(jīng)典變體也是面試高頻題。題目要求返回一個(gè)新的數(shù)組counts其中counts[i]的值是nums[i]右側(cè)小于nums[i]的元素的數(shù)量。分析這本質(zhì)上就是求“以每個(gè)元素為左元素的逆序?qū)Α睌?shù)量。標(biāo)準(zhǔn)逆序數(shù)模板求得是總數(shù)。我們需要為每個(gè)元素單獨(dú)計(jì)數(shù)。思路是在歸并排序的過(guò)程中元素的位置會(huì)發(fā)生變化我們需要一種方法在元素移動(dòng)時(shí)還能知道它是誰(shuí)并更新它的計(jì)數(shù)。解決方案使用“索引數(shù)組”。我們不對(duì)原始值數(shù)組nums進(jìn)行排序而是對(duì)一個(gè)索引數(shù)組indexes進(jìn)行排序。排序的比較規(guī)則是基于nums[indexes[i]]的值。在合并過(guò)程中當(dāng)我們將一個(gè)右半部分的索引對(duì)應(yīng)原數(shù)組某個(gè)元素放入臨時(shí)數(shù)組時(shí)意味著這個(gè)右半部分的元素比當(dāng)前左半部分剩余的所有元素都“小”在排序意義上。那么這些左半部分剩余元素對(duì)應(yīng)的原數(shù)組位置其“右側(cè)小于它的數(shù)量”就應(yīng)該增加 1。但注意右半部分的元素在原數(shù)組中確實(shí)是在左側(cè)元素的右邊。實(shí)現(xiàn)要點(diǎn)創(chuàng)建vectorint indexes(n)初始為[0, 1, 2, ..., n-1]。vectorint count(n, 0)記錄結(jié)果。歸并排序的對(duì)象是indexes數(shù)組。比較時(shí)用nums[indexes[i]]。在合并的else分支即nums[indexes[i]] nums[indexes[j]]時(shí)我們需要更新計(jì)數(shù)。但這里更新的不是indexes[j]而是左半部分所有剩余元素對(duì)應(yīng)的計(jì)數(shù)。因?yàn)閕ndexes[j]來(lái)自右半部分它小于左半部分當(dāng)前及之后的所有元素所以這些左半部分的元素其“右側(cè)小元素”數(shù)量都應(yīng)該 1。更高效的做法是在將右半部分元素放入臨時(shí)數(shù)組時(shí)用一個(gè)變量記錄本次從右半部分取出了多少個(gè)元素記為right_count在后續(xù)將左半部分元素放入臨時(shí)數(shù)組時(shí)將其計(jì)數(shù)增加right_count。但更清晰的做法是在else分支中直接遍歷左半部分剩余元素增加計(jì)數(shù)。為了效率我們通常采用一個(gè)“計(jì)數(shù)器”累加的方式。這道題的實(shí)現(xiàn)細(xì)節(jié)比標(biāo)準(zhǔn)模板復(fù)雜但它完美體現(xiàn)了歸并排序分治思想在解決“帶位置信息計(jì)數(shù)”問(wèn)題上的強(qiáng)大能力。通過(guò)練習(xí)這道題你對(duì)逆序數(shù)模板的理解會(huì)從“求和”深入到“分配”的層面。6. 性能分析與橫向?qū)Ρ葹槭裁词菤w并排序我們已經(jīng)實(shí)現(xiàn)了模板也看到了它的應(yīng)用?，F(xiàn)在我們來(lái)深入分析一下為什么歸并排序是解決逆序數(shù)問(wèn)題的“天選之子”以及其他方法為什么不行。6.1 時(shí)間復(fù)雜度O(n log n) 的必然性歸并排序的時(shí)間復(fù)雜度是 O(n log n)這是基于比較的排序算法的下限。計(jì)算逆序數(shù)本質(zhì)上是一個(gè)基于比較的計(jì)數(shù)問(wèn)題它至少需要讀取所有數(shù)據(jù)其時(shí)間復(fù)雜度下限也是 O(n log n)可以通過(guò)決策樹(shù)模型證明。因此歸并排序方案是漸進(jìn)最優(yōu)的。暴力法 O(n2)數(shù)據(jù)量稍大如 n10^5就完全不可行。樹(shù)狀數(shù)組/二叉索引樹(shù) (Fenwick Tree) O(n log n)這也是一個(gè)非常優(yōu)秀的解法。其思路是離散化數(shù)組值后從右向左遍歷查詢(xún)當(dāng)前值之前有多少個(gè)小于它的數(shù)即前綴和然后更新樹(shù)狀數(shù)組。它的復(fù)雜度也是 O(n log n)且常數(shù)很小。與歸并排序相比它需要額外的離散化步驟和 O(n) 的空間。兩種方法在時(shí)間復(fù)雜度上打平歸并排序的優(yōu)勢(shì)在于其思路與排序過(guò)程天然結(jié)合更直觀體現(xiàn)分治思想。線段樹(shù)同樣可以解決但代碼量通常比樹(shù)狀數(shù)組和歸并排序都要大在此問(wèn)題上不是最簡(jiǎn)潔的選擇。6.2 空間復(fù)雜度O(n) 的權(quán)衡歸并排序需要 O(n) 的額外空間臨時(shí)數(shù)組temp。這是一個(gè)典型的“以空間換時(shí)間”的策略。在絕大多數(shù)算法競(jìng)賽和面試場(chǎng)景中空間限制通常是寬松的如 256MB 或 512MBO(n) 的空間消耗對(duì)于 n 高達(dá) 10^6 是完全可以接受的。樹(shù)狀數(shù)組解法也需要 O(n) 的空間用于存儲(chǔ)樹(shù)狀結(jié)構(gòu)。因此在空間復(fù)雜度上兩者也是打平的。6.3 穩(wěn)定性與可擴(kuò)展性歸并排序是穩(wěn)定的排序算法。這在某些變體問(wèn)題中很重要例如當(dāng)數(shù)組元素相同時(shí)穩(wěn)定的排序能保證我們不會(huì)多算或少算逆序?qū)Ω鶕?jù)問(wèn)題定義相等通常不構(gòu)成逆序。樹(shù)狀數(shù)組解法本身與排序穩(wěn)定性無(wú)關(guān)。在可擴(kuò)展性方面歸并排序的框架更容易嵌入其他復(fù)雜的統(tǒng)計(jì)邏輯正如我們?cè)?LeetCode 493 題中做的那樣——在合并前增加一個(gè)統(tǒng)計(jì)步驟。這種“分治-統(tǒng)計(jì)-合并”的模式非常清晰。而樹(shù)狀數(shù)組更擅長(zhǎng)處理動(dòng)態(tài)的前綴和查詢(xún)與更新對(duì)于復(fù)雜的跨區(qū)間統(tǒng)計(jì)有時(shí)不如歸并排序框架直觀。7. 模板的終極記憶法與編碼肌肉記憶最后我們來(lái)談?wù)勅绾握嬲莆者@個(gè)模板達(dá)到在面試或競(jìng)賽中能快速、準(zhǔn)確寫(xiě)出來(lái)的程度。死記硬背是不可靠的理解基礎(chǔ)上的“肌肉記憶”才是關(guān)鍵。記憶要點(diǎn)拆解函數(shù)簽名LL mergeSortAndCount(vectorint nums, int left, int right, vectorint temp)。記住需要原數(shù)組、左右邊界、臨時(shí)數(shù)組。遞歸基if (left right) return 0;計(jì)算中點(diǎn)int mid left (right - left) / 2;遞歸調(diào)用累加左右結(jié)果。合并前初始化指針ileft, jmid1, kleft。核心 while 循環(huán)if (nums[i] nums[j]): 放nums[i]i。else:累加逆序數(shù)inv_count (mid - i 1)放nums[j]j。收尾循環(huán)把剩下的i或j部分拷貝完。拷貝回原數(shù)組for (idx from left to right) nums[idx] temp[idx]。返回總逆序數(shù)。編碼練習(xí)建議白板練習(xí)在紙上或白板上不參考任何資料從零開(kāi)始默寫(xiě)整個(gè)函數(shù)。寫(xiě)完后對(duì)照檢查。閉眼模擬在腦子里模擬一個(gè)簡(jiǎn)單數(shù)組如[3, 1, 2]的整個(gè)遞歸、合并、計(jì)數(shù)過(guò)程。想象調(diào)用棧、指針移動(dòng)和inv_count的變化。變體挑戰(zhàn)嘗試修改模板去解決 LeetCode 315 或 493。即使一開(kāi)始寫(xiě)不出來(lái)思考的過(guò)程也能極大加深理解。定時(shí)訓(xùn)練設(shè)定 5-7 分鐘目標(biāo)是能一次性無(wú)錯(cuò)寫(xiě)出標(biāo)準(zhǔn)模板。速度和質(zhì)量并重。當(dāng)你經(jīng)過(guò)多次練習(xí)后你會(huì)發(fā)現(xiàn)這個(gè)模板就像一段旋律一樣刻在腦子里。它的核心邏輯——在合并有序序列時(shí)利用有序性批量計(jì)數(shù)跨區(qū)間逆序?qū)Α獙⒊蔀槟憬鉀Q一系列分治計(jì)數(shù)問(wèn)題的強(qiáng)大思維工具。這遠(yuǎn)遠(yuǎn)超越了一道題本身而是掌握了一種重要的算法范式。