到分治O(n log n)的算法优化)
第一次刷到“交易逆序对的总数(6)”这道题时我愣了几秒钟——交易逆序对后来仔细一看题面其实就是经典数组逆序对统计题号后面的“(6)”大概只是题库里的序号跟难度没有直接关系。逆序对的定义很简单对于数组nums如果存在i j且nums[i] nums[j]那(i,j)就算一对。统计整个数组有多少对这样的组合看起来朴素但它是分治思想最好的入门练习题之一也是面试里反复出现的考察点。数组规模一旦到十万、百万O(n²) 的两层循环铁定超时只有归并排序配合分治才能把复杂度稳定压到 O(n log n)。这篇文章我会把暴力解、分治原理、完整代码、易错点一次聊透适合刚学算法的人也适合准备刷题面试的人参考。1. 先说清楚逆序对的定义以及暴力解为什么走不通1.1 用手数一遍理解“逆序”到底指什么我们先拿一个具体数组[7,5,6,4]来数。下标从0开始所有下标对一共 C(4,2)6 对其中满足前面元素大于后面元素的是75、76、74、54、64一共5对。注意5和6这组是56不满足两个相等的元素比如[1,1]也不算逆序对必须是严格大于。这里“严格大于”四个字看着不起眼但在代码里如果写错等号结果会差很多后面我会专门讲。逆序对数量在数学上叫逆序数它描述的是一个数组相对于升序排列的“错乱程度”。一个完全升序的数组逆序对数为0一个完全降序的数组逆序对数为n*(n-1)/2也就是任意两个位置都构成一个逆序对。这个特性很有用平时验证代码对不对可以直接构造几个特殊数组升序数组答案必须是0降序数组答案必须是n*(n-1)/2重复数组则要看严格大于条件。1.2 暴力两层循环5行代码解决但只配当玩具暴力法的思路没有任何弯子枚举所有ij判断nums[i]是否大于nums[j]。Python 写出来就是这样def count_inversions_bruteforce(nums): n len(nums) ans 0 for i in range(n): for j in range(i 1, n): if nums[i] nums[j]: ans 1 return ans这段代码的正确性不用怀疑拿来对拍、验证优化算法非常顺手。但它的问题是复杂度 O(n²)。当n10^5时最坏情况需要比较大约5×10^9次即使 C 也未必能在一两秒内跑完Python 更是直接劝退。所以生产中不可能用暴力算法竞赛和面试更不可能把 O(n²) 当作最终答案。一旦意识到“每个元素对都被重复比较了很多次”自然就会想到分治能不能让每一对元素只被少量几次操作覆盖而不是全量枚举。2. 分治为什么能优化逆序对统计2.1 分治三步骤和逆序对的天然对应分治算法的经典流程是先分解、再解决、再合并。对数组从中间劈开成左右两半先分别递归求出左半段内部的逆序对数和右半段内部的逆序对数然后只需要额外统计“一个元素在左半段、另一个元素在右半段”的跨区间逆序对三者相加就是答案。正是因为任意逆序对只有三种归属全在左、全在右、一左一右所以分治可以把问题自然地拆成互不重叠的三个部分不会重复也不会遗漏。这里有一点容易被忽略左右两半的内部逆序对在递归求子数组排序时已经统计完了真正需要动脑筋的是跨区间部分。如果直接暴力统计跨区间复杂度又会回到 O(n²)因为每个左半元素都可能和右半元素比较。分治的妙处在于递归函数在返回之前已经把左右子数组都排成升序这样合并左半和右半的时候就能利用“有序”来批量计数把 O(n²) 的比较压缩成 O(n)。2.2 合并有序数组时怎么“顺便”把逆序对算完过程可以这样看。假设左半有序数组是L右半有序数组是R我们用一个归并循环把它们合并成完整的有序数组。维护两个指针i和j分别指向当前正在比较的L元素和R元素。如果L[i] R[j]说明L[i]不大于右半当前元素又因为R是有序的R[j]后面的元素都比R[j]大所以L[i]不会和R[j]以及它后面的任何元素构成逆序对。此时直接把L[i]放到合并结果里i后移。如果L[i] R[j]说明R[j]小于当前左半元素。更关键的是因为L是有序的L[i]后面所有的元素都不会小于L[i]自然也都大于R[j]。这些左半元素在原始数组中的位置都在R[j]的左侧值又都比它大所以每一个都和R[j]构成一个逆序对。也就是说当遇到这个情况时可以一次性加上“左半剩余元素个数”个逆序对然后把R[j]放入合并结果j后移。这个技巧就是整道题的核心。举一个小例子如果左半是[5,7]右半是[4,6]合并时第一次比较5和454于是5和7这两个左半元素都与4构成逆序对一次性加2后面5和6比较56不计数7和6比较76再加1。总计跨区间逆序对3个加上左右半段内部的逆序对就得到了完整答案。2.3 为什么标配是归并排序而不是快速排序分治算法一大把快速排序也是分治但很少有人用快排统计逆序对。原因在于快排在 partition 之后pivot 左右两侧虽然满足大小关系但各自内部并不保证有序。你在 partition 过程中根本不知道某个右侧元素前面到底还剩多少个左侧元素比它大所以没有办法批量计数。而归并排序的合并阶段面对的是两个有序数组可以沿着“有序性”这条线一次性扫描完成统计。换句话说不是所有分治都适合统计逆序对归并排序的形态天生契合这个需求。顺带说一句网上常能看到“分治法求一个n元素数组中最大元素的位置”这也是分治的入门小例子做法是把数组分为两半分别求最大再比较两个最大值返回位置。它和逆序对统计没有直接关系但能帮初学者理解“分解-解决-合并”的框架。3. 完整代码和一步步推演3.1 C 版本最常用、也最容易写错先给一份能直接跑的 C 代码。为了在递归里不反复申请大数组我用一个临时vector存放合并结果合并完再写回原数组对应区间。#include vector #include cstdio using namespace std; long long mergeSortCount(vectorint nums, int left, int right) { if (left right) return 0; int mid left (right - left) / 2; long long cnt mergeSortCount(nums, left, mid) mergeSortCount(nums, mid 1, right); vectorint tmp(right - left 1); int i left; int j mid 1; int k 0; while (i mid j right) { if (nums[i] nums[j]) { tmp[k] nums[i]; } else { cnt mid - i 1; tmp[k] nums[j]; } } while (i mid) tmp[k] nums[i]; while (j right) tmp[k] nums[j]; for (int p 0; p (int)tmp.size(); p) { nums[left p] tmp[p]; } return cnt; } int main() { vectorint nums {7,5,6,4}; long long ans mergeSortCount(nums, 0, (int)nums.size() - 1); printf(%lld\n, ans); return 0; }这份代码里最关键的一行就是cnt mid - i 1。因为当前区间下标是闭区间[left,right]左半部分是[left,mid]所以当右指针指向的元素小于nums[i]时左半从i到mid一共还剩mid-i1个元素它们全都在原位置排在当前右元素之前且值都比它大所以全部计入答案。用long long承接答案是因为最坏情况逆序对数量接近n²/2int很容易溢出。3.2 Python 版本更容易照葫芦画瓢很多刷题场景用 Python代码风格可以更简洁。下面的版本拆成两半分别递归再把结果合并最后返回排序后的数组和逆序对数。def merge_sort_count(nums): if len(nums) 1: return nums, 0 mid len(nums) // 2 left, cnt_l merge_sort_count(nums[:mid]) right, cnt_r merge_sort_count(nums[mid:]) merged [] i j 0 cnt cnt_l cnt_r m, n len(left), len(right) while i m and j n: if left[i] right[j]: merged.append(left[i]) i 1 else: cnt m - i merged.append(right[j]) j 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged, cntPython 版本因为没有int溢出问题数字再大也能撑住但要注意切片会让空间开销增加。如果在内存极敏感的工程里更推荐用 C 那种传下标的方式。不过面试现场用这种写法的好处是直观每层递归都返回排好序的数组计数规则一眼就能看懂。3.3 手推一遍[7,5,6,4]看答案怎么凑出来还是用刚才的例子。第一次分解得到[7,5]和[6,4]继续分解到单元素[7]、[5]、[6]、[4]。合并[7]和[5]75左半还剩1个元素所以跨区间逆序对 1得到有序数组[5,7]。 合并[6]和[4]64同样 1得到[4,6]。 最后合并[5,7]和[4,6]54左半元素是5、7剩余2个所以 2右侧4进入结果j移到656左侧5进入结果i移到776左半剩余1个所以 1右侧6进入结果 最后把7放入合并得到[4,5,6,7]。整个过程中cnt是11215和最开始手数的答案完全一致。注意第二次合并时74和76这两个逆序对并不是靠两次独立比较得到的当54时机器已经通过“批量计数”把7也一起算进去了。这种批量感就是分治算法效率的来源。3.4 复杂度小结归并排序求逆序对的时间复杂度是 O(n log n)因为每次合并把所有元素扫一遍递归深度是 log n空间复杂度是 O(n)主要来自临时数组递归栈只占 O(log n)。它不会改变原数组的相对顺序所以是一种稳定排序。相比暴力 O(n²)n 越大优势越明显。当n从1万涨到100万暴力几乎不可用而归并排序只需要约2000万次操作任何现代语言都能轻松跑完。4. 从“交易逆序对”到其他算法这个问题远不止一种解法4.1 先别把“字符串逆序”和“逆序对”混为一谈在相关搜索里看到很多人找“字符串逆序 c语言”“字符串逆序输出”之类的内容这里必须提醒一下字符串逆序是把整体字符倒过来比如abc变成cba这属于字符串操作而逆序对是统计数组中“前面比后面大”的对子数量属于排列性质。两者只有“逆序”两个字相同思路完全不同。如果你在网上搜资料发现自己写的代码怎么都对不上答案先看看是不是把这两个概念弄混了。字符串逆序通常用双指针或者栈就能解决逆序对则需要分治或树状数组复杂度也不在一个量级。4.2 为什么题目要叫“交易逆序对的总数”这道题的本质只是数组逆序对统计但题面偏偏带上了“交易”两个字让不少人一开始摸不着头脑。类比到实际场景逆序对确实能描述金融序列里的“无序程度”把股票每日价格按时间排成数组如果出现某天价格比之后某天高那就在时间序列上形成一个“高点在后”的反向关系逆序对数量越多说明价格回调越频繁走势越不稳定。很多量化分析会用类似概念衡量价格序列和某个基准序列的偏离程度。当然刷题时不用想这么复杂把“交易”当成包装直接抽象成数组就行。4.3 树状数组求逆序对另一种高频思路除了归并排序树状数组Binary Indexed Tree也是求逆序对的常见解法而且在某些动态求逆序对的问题里更灵活。基本步骤是先对数组做离散化把所有元素映射到1..m的排名然后从右往左遍历原数组每遇到一个元素就查询树状数组中值域在它左侧的所有已出现元素个数这些元素都位于它右侧但值比它小因此全部构成逆序对累加后把当前位置的排名插入树状数组。这样同样是 O(n log n)但代码更偏向数据结构。举个例子数组[7,5,6,4]离散化后值域排名是4,2,3,1。从右往左遍历到4排名1查询比1小的没有插入1遍历到6排名3查询比3小的已出现元素有排名1所以 1插入3遍历到5排名2查询比2小的有排名11插入2遍历到7排名4查询比4小的有1、2、33。总计5结果一致。4.4 现实中的用途逆序对不是只有笔试才用逆序对在实际工程里也有不少影子。第一它能衡量一个序列离“完全有序”有多远很多排序算法比如插入排序的交换次数就等于逆序对数所以知道了初始逆序对就能预估某些排序算法的实际性能。第二在推荐系统里把“时间顺序”和“模型打分顺序”两个序列放在一起算逆序对可以量化推荐结果对时间因素的破坏程度。第三在数据库维护有序索引时逆序对数量也常被用来估算索引是否需要重建。虽然不是每个业务都会直接调用求逆序对的函数但它的思想已经渗透到很多排序和统计场景中。5. 实际踩坑记录和面试防身术5.1 等号问题重复元素最容易翻车统计逆序对必须满足严格大于所以相等不能计数。以数组[1,2,2,1]为例正确答案是两对两个位置的2分别和最后一个1构成逆序对。合并时如果写成nums[i] nums[j]那么当nums[i]2、nums[j]2时也会进入 else 分支错误地把相等的两个2也算成逆序对答案就会偏大。记住合并比较时用的是遇到相等时先放左半元素让右半元素继续跟后面的左半元素比较。这个细节在面试手写代码时非常容易被追问务必注意。5.2 边界条件left、mid、right 一定不能重递归函数里最容易写错的是mid和mid1的边界。如果right-left是0或负数直接返回0mid用left (right-left)/2可以避免整数溢出。在 while 循环里左半段的区间是[left, mid]右半段是[mid1, right]写合并复制回原数组时要保证下标一一对应。很多初学的人会出现“合并到一半数组越界”或者“排序完发现数组少了一块”的诡异现象基本都是边界考虑不周。建议每次写完都先用一个随机数组做对拍确认原数组被完整排序。5.3 返回值记得用长整型一个很容易被忽略的坑是当n达到10^5时完全逆序的数组答案n*(n-1)/2大约是4.99995×10^9已经超过int上界。如果题目没有特殊说明用int接收返回结果会在线判定上拿到 Wrong Answer而且这种 WA 非常难排查因为直觉上“数一数能有多少对”也不会想到会溢出。C 里最好统一使用long longJava 用long只有 Python 可以放心使用int。养成习惯别在这么基础的地方丢分。5.4 副作用归并排序会把原数组改掉很多人的主函数里先定义好nums然后调用统计函数完事之后还想继续用nums做别的事结果发现nums已经被排好序了。因为归并排序本质上是把数组逐渐变成有序过程中会写入临时结果。如果不想影响原数组可以在统计函数入口先复制一份例如 C 里long long countInversions(vectorint nums) { vectorint work nums; return mergeSortCount(work, 0, (int)work.size() - 1); }这个封装看似简单却能在联调时避免不少“数据被改了”的离谱问题。5.5 调试速查表为了方便复习我把常见的错误状态整理成了一个表症状可能原因解决方法答案整体偏大把相等的数也当成逆序对统计合并时使用不能用答案偏小只统计了单个左元素而不是剩余左元素确认用的是mid - i 1答案不稳定递归子问题写成了左闭右开或左右交叉统一区间表示法推荐闭区间越界或排序错乱临时数组长度或复制起点算错检查tmp[right-left1]与nums[leftp]大样例超时还在用 O(n²) 暴力换成归并排序或树状数组WA 且样例很小返回值溢出了 int改用long long/long这张表我每次面试前都会扫一遍基本能覆盖所有新手常见问题。5.6 说说我自己的理解方式最后分享一个个人体会。归并排序求逆序对网上模板满天飞但很多人背完以后一星期就忘。我后来发现真正让它记住的不是那一行cnt mid - i 1而是一个画面合并两个有序数组时右边弹出一个数左边还剩多少个数没有弹出这些数全都比它大而且全都排在它前面所以每一个都是它制造的逆序对。把“还剩几个、就加几个”这六个字理解透分治求逆序对就不再是模板题而是一道随时可以推出来的基础题。
逆序对统计与归并排序：从暴力O(n²)到分治O(n log n)的算法优化
第一次刷到“交易逆序对的总数(6)”这道题时我愣了几秒钟——交易逆序对后来仔细一看题面其实就是经典数组逆序对统计题号后面的“(6)”大概只是题库里的序号跟难度没有直接关系。逆序对的定义很简单对于数组nums如果存在i j且nums[i] nums[j]那(i,j)就算一对。统计整个数组有多少对这样的组合看起来朴素但它是分治思想最好的入门练习题之一也是面试里反复出现的考察点。数组规模一旦到十万、百万O(n²) 的两层循环铁定超时只有归并排序配合分治才能把复杂度稳定压到 O(n log n)。这篇文章我会把暴力解、分治原理、完整代码、易错点一次聊透适合刚学算法的人也适合准备刷题面试的人参考。1. 先说清楚逆序对的定义以及暴力解为什么走不通1.1 用手数一遍理解“逆序”到底指什么我们先拿一个具体数组[7,5,6,4]来数。下标从0开始所有下标对一共 C(4,2)6 对其中满足前面元素大于后面元素的是75、76、74、54、64一共5对。注意5和6这组是56不满足两个相等的元素比如[1,1]也不算逆序对必须是严格大于。这里“严格大于”四个字看着不起眼但在代码里如果写错等号结果会差很多后面我会专门讲。逆序对数量在数学上叫逆序数它描述的是一个数组相对于升序排列的“错乱程度”。一个完全升序的数组逆序对数为0一个完全降序的数组逆序对数为n*(n-1)/2也就是任意两个位置都构成一个逆序对。这个特性很有用平时验证代码对不对可以直接构造几个特殊数组升序数组答案必须是0降序数组答案必须是n*(n-1)/2重复数组则要看严格大于条件。1.2 暴力两层循环5行代码解决但只配当玩具暴力法的思路没有任何弯子枚举所有ij判断nums[i]是否大于nums[j]。Python 写出来就是这样def count_inversions_bruteforce(nums): n len(nums) ans 0 for i in range(n): for j in range(i 1, n): if nums[i] nums[j]: ans 1 return ans这段代码的正确性不用怀疑拿来对拍、验证优化算法非常顺手。但它的问题是复杂度 O(n²)。当n10^5时最坏情况需要比较大约5×10^9次即使 C 也未必能在一两秒内跑完Python 更是直接劝退。所以生产中不可能用暴力算法竞赛和面试更不可能把 O(n²) 当作最终答案。一旦意识到“每个元素对都被重复比较了很多次”自然就会想到分治能不能让每一对元素只被少量几次操作覆盖而不是全量枚举。2. 分治为什么能优化逆序对统计2.1 分治三步骤和逆序对的天然对应分治算法的经典流程是先分解、再解决、再合并。对数组从中间劈开成左右两半先分别递归求出左半段内部的逆序对数和右半段内部的逆序对数然后只需要额外统计“一个元素在左半段、另一个元素在右半段”的跨区间逆序对三者相加就是答案。正是因为任意逆序对只有三种归属全在左、全在右、一左一右所以分治可以把问题自然地拆成互不重叠的三个部分不会重复也不会遗漏。这里有一点容易被忽略左右两半的内部逆序对在递归求子数组排序时已经统计完了真正需要动脑筋的是跨区间部分。如果直接暴力统计跨区间复杂度又会回到 O(n²)因为每个左半元素都可能和右半元素比较。分治的妙处在于递归函数在返回之前已经把左右子数组都排成升序这样合并左半和右半的时候就能利用“有序”来批量计数把 O(n²) 的比较压缩成 O(n)。2.2 合并有序数组时怎么“顺便”把逆序对算完过程可以这样看。假设左半有序数组是L右半有序数组是R我们用一个归并循环把它们合并成完整的有序数组。维护两个指针i和j分别指向当前正在比较的L元素和R元素。如果L[i] R[j]说明L[i]不大于右半当前元素又因为R是有序的R[j]后面的元素都比R[j]大所以L[i]不会和R[j]以及它后面的任何元素构成逆序对。此时直接把L[i]放到合并结果里i后移。如果L[i] R[j]说明R[j]小于当前左半元素。更关键的是因为L是有序的L[i]后面所有的元素都不会小于L[i]自然也都大于R[j]。这些左半元素在原始数组中的位置都在R[j]的左侧值又都比它大所以每一个都和R[j]构成一个逆序对。也就是说当遇到这个情况时可以一次性加上“左半剩余元素个数”个逆序对然后把R[j]放入合并结果j后移。这个技巧就是整道题的核心。举一个小例子如果左半是[5,7]右半是[4,6]合并时第一次比较5和454于是5和7这两个左半元素都与4构成逆序对一次性加2后面5和6比较56不计数7和6比较76再加1。总计跨区间逆序对3个加上左右半段内部的逆序对就得到了完整答案。2.3 为什么标配是归并排序而不是快速排序分治算法一大把快速排序也是分治但很少有人用快排统计逆序对。原因在于快排在 partition 之后pivot 左右两侧虽然满足大小关系但各自内部并不保证有序。你在 partition 过程中根本不知道某个右侧元素前面到底还剩多少个左侧元素比它大所以没有办法批量计数。而归并排序的合并阶段面对的是两个有序数组可以沿着“有序性”这条线一次性扫描完成统计。换句话说不是所有分治都适合统计逆序对归并排序的形态天生契合这个需求。顺带说一句网上常能看到“分治法求一个n元素数组中最大元素的位置”这也是分治的入门小例子做法是把数组分为两半分别求最大再比较两个最大值返回位置。它和逆序对统计没有直接关系但能帮初学者理解“分解-解决-合并”的框架。3. 完整代码和一步步推演3.1 C 版本最常用、也最容易写错先给一份能直接跑的 C 代码。为了在递归里不反复申请大数组我用一个临时vector存放合并结果合并完再写回原数组对应区间。#include vector #include cstdio using namespace std; long long mergeSortCount(vectorint nums, int left, int right) { if (left right) return 0; int mid left (right - left) / 2; long long cnt mergeSortCount(nums, left, mid) mergeSortCount(nums, mid 1, right); vectorint tmp(right - left 1); int i left; int j mid 1; int k 0; while (i mid j right) { if (nums[i] nums[j]) { tmp[k] nums[i]; } else { cnt mid - i 1; tmp[k] nums[j]; } } while (i mid) tmp[k] nums[i]; while (j right) tmp[k] nums[j]; for (int p 0; p (int)tmp.size(); p) { nums[left p] tmp[p]; } return cnt; } int main() { vectorint nums {7,5,6,4}; long long ans mergeSortCount(nums, 0, (int)nums.size() - 1); printf(%lld\n, ans); return 0; }这份代码里最关键的一行就是cnt mid - i 1。因为当前区间下标是闭区间[left,right]左半部分是[left,mid]所以当右指针指向的元素小于nums[i]时左半从i到mid一共还剩mid-i1个元素它们全都在原位置排在当前右元素之前且值都比它大所以全部计入答案。用long long承接答案是因为最坏情况逆序对数量接近n²/2int很容易溢出。3.2 Python 版本更容易照葫芦画瓢很多刷题场景用 Python代码风格可以更简洁。下面的版本拆成两半分别递归再把结果合并最后返回排序后的数组和逆序对数。def merge_sort_count(nums): if len(nums) 1: return nums, 0 mid len(nums) // 2 left, cnt_l merge_sort_count(nums[:mid]) right, cnt_r merge_sort_count(nums[mid:]) merged [] i j 0 cnt cnt_l cnt_r m, n len(left), len(right) while i m and j n: if left[i] right[j]: merged.append(left[i]) i 1 else: cnt m - i merged.append(right[j]) j 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged, cntPython 版本因为没有int溢出问题数字再大也能撑住但要注意切片会让空间开销增加。如果在内存极敏感的工程里更推荐用 C 那种传下标的方式。不过面试现场用这种写法的好处是直观每层递归都返回排好序的数组计数规则一眼就能看懂。3.3 手推一遍[7,5,6,4]看答案怎么凑出来还是用刚才的例子。第一次分解得到[7,5]和[6,4]继续分解到单元素[7]、[5]、[6]、[4]。合并[7]和[5]75左半还剩1个元素所以跨区间逆序对 1得到有序数组[5,7]。 合并[6]和[4]64同样 1得到[4,6]。 最后合并[5,7]和[4,6]54左半元素是5、7剩余2个所以 2右侧4进入结果j移到656左侧5进入结果i移到776左半剩余1个所以 1右侧6进入结果 最后把7放入合并得到[4,5,6,7]。整个过程中cnt是11215和最开始手数的答案完全一致。注意第二次合并时74和76这两个逆序对并不是靠两次独立比较得到的当54时机器已经通过“批量计数”把7也一起算进去了。这种批量感就是分治算法效率的来源。3.4 复杂度小结归并排序求逆序对的时间复杂度是 O(n log n)因为每次合并把所有元素扫一遍递归深度是 log n空间复杂度是 O(n)主要来自临时数组递归栈只占 O(log n)。它不会改变原数组的相对顺序所以是一种稳定排序。相比暴力 O(n²)n 越大优势越明显。当n从1万涨到100万暴力几乎不可用而归并排序只需要约2000万次操作任何现代语言都能轻松跑完。4. 从“交易逆序对”到其他算法这个问题远不止一种解法4.1 先别把“字符串逆序”和“逆序对”混为一谈在相关搜索里看到很多人找“字符串逆序 c语言”“字符串逆序输出”之类的内容这里必须提醒一下字符串逆序是把整体字符倒过来比如abc变成cba这属于字符串操作而逆序对是统计数组中“前面比后面大”的对子数量属于排列性质。两者只有“逆序”两个字相同思路完全不同。如果你在网上搜资料发现自己写的代码怎么都对不上答案先看看是不是把这两个概念弄混了。字符串逆序通常用双指针或者栈就能解决逆序对则需要分治或树状数组复杂度也不在一个量级。4.2 为什么题目要叫“交易逆序对的总数”这道题的本质只是数组逆序对统计但题面偏偏带上了“交易”两个字让不少人一开始摸不着头脑。类比到实际场景逆序对确实能描述金融序列里的“无序程度”把股票每日价格按时间排成数组如果出现某天价格比之后某天高那就在时间序列上形成一个“高点在后”的反向关系逆序对数量越多说明价格回调越频繁走势越不稳定。很多量化分析会用类似概念衡量价格序列和某个基准序列的偏离程度。当然刷题时不用想这么复杂把“交易”当成包装直接抽象成数组就行。4.3 树状数组求逆序对另一种高频思路除了归并排序树状数组Binary Indexed Tree也是求逆序对的常见解法而且在某些动态求逆序对的问题里更灵活。基本步骤是先对数组做离散化把所有元素映射到1..m的排名然后从右往左遍历原数组每遇到一个元素就查询树状数组中值域在它左侧的所有已出现元素个数这些元素都位于它右侧但值比它小因此全部构成逆序对累加后把当前位置的排名插入树状数组。这样同样是 O(n log n)但代码更偏向数据结构。举个例子数组[7,5,6,4]离散化后值域排名是4,2,3,1。从右往左遍历到4排名1查询比1小的没有插入1遍历到6排名3查询比3小的已出现元素有排名1所以 1插入3遍历到5排名2查询比2小的有排名11插入2遍历到7排名4查询比4小的有1、2、33。总计5结果一致。4.4 现实中的用途逆序对不是只有笔试才用逆序对在实际工程里也有不少影子。第一它能衡量一个序列离“完全有序”有多远很多排序算法比如插入排序的交换次数就等于逆序对数所以知道了初始逆序对就能预估某些排序算法的实际性能。第二在推荐系统里把“时间顺序”和“模型打分顺序”两个序列放在一起算逆序对可以量化推荐结果对时间因素的破坏程度。第三在数据库维护有序索引时逆序对数量也常被用来估算索引是否需要重建。虽然不是每个业务都会直接调用求逆序对的函数但它的思想已经渗透到很多排序和统计场景中。5. 实际踩坑记录和面试防身术5.1 等号问题重复元素最容易翻车统计逆序对必须满足严格大于所以相等不能计数。以数组[1,2,2,1]为例正确答案是两对两个位置的2分别和最后一个1构成逆序对。合并时如果写成nums[i] nums[j]那么当nums[i]2、nums[j]2时也会进入 else 分支错误地把相等的两个2也算成逆序对答案就会偏大。记住合并比较时用的是遇到相等时先放左半元素让右半元素继续跟后面的左半元素比较。这个细节在面试手写代码时非常容易被追问务必注意。5.2 边界条件left、mid、right 一定不能重递归函数里最容易写错的是mid和mid1的边界。如果right-left是0或负数直接返回0mid用left (right-left)/2可以避免整数溢出。在 while 循环里左半段的区间是[left, mid]右半段是[mid1, right]写合并复制回原数组时要保证下标一一对应。很多初学的人会出现“合并到一半数组越界”或者“排序完发现数组少了一块”的诡异现象基本都是边界考虑不周。建议每次写完都先用一个随机数组做对拍确认原数组被完整排序。5.3 返回值记得用长整型一个很容易被忽略的坑是当n达到10^5时完全逆序的数组答案n*(n-1)/2大约是4.99995×10^9已经超过int上界。如果题目没有特殊说明用int接收返回结果会在线判定上拿到 Wrong Answer而且这种 WA 非常难排查因为直觉上“数一数能有多少对”也不会想到会溢出。C 里最好统一使用long longJava 用long只有 Python 可以放心使用int。养成习惯别在这么基础的地方丢分。5.4 副作用归并排序会把原数组改掉很多人的主函数里先定义好nums然后调用统计函数完事之后还想继续用nums做别的事结果发现nums已经被排好序了。因为归并排序本质上是把数组逐渐变成有序过程中会写入临时结果。如果不想影响原数组可以在统计函数入口先复制一份例如 C 里long long countInversions(vectorint nums) { vectorint work nums; return mergeSortCount(work, 0, (int)work.size() - 1); }这个封装看似简单却能在联调时避免不少“数据被改了”的离谱问题。5.5 调试速查表为了方便复习我把常见的错误状态整理成了一个表症状可能原因解决方法答案整体偏大把相等的数也当成逆序对统计合并时使用不能用答案偏小只统计了单个左元素而不是剩余左元素确认用的是mid - i 1答案不稳定递归子问题写成了左闭右开或左右交叉统一区间表示法推荐闭区间越界或排序错乱临时数组长度或复制起点算错检查tmp[right-left1]与nums[leftp]大样例超时还在用 O(n²) 暴力换成归并排序或树状数组WA 且样例很小返回值溢出了 int改用long long/long这张表我每次面试前都会扫一遍基本能覆盖所有新手常见问题。5.6 说说我自己的理解方式最后分享一个个人体会。归并排序求逆序对网上模板满天飞但很多人背完以后一星期就忘。我后来发现真正让它记住的不是那一行cnt mid - i 1而是一个画面合并两个有序数组时右边弹出一个数左边还剩多少个数没有弹出这些数全都比它大而且全都排在它前面所以每一个都是它制造的逆序对。把“还剩几个、就加几个”这六个字理解透分治求逆序对就不再是模板题而是一道随时可以推出来的基础题。
