1. 先把题意拆开这不是单纯的排序题看到“计算右侧小于当前元素的个数”这个标题我第一反应是又遇到一道“披着排序外衣的统计题”。题目本身不复杂给你一个数组nums对每个位置i统计所有满足j i并且nums[j] nums[i]的元素个数。比如[5,2,6,1]的结果是[2,1,1,0]5 右侧比 5 小的是 2 和 1所以是 22 右侧比 2 小的是 16 右侧比 6 小的是 11 右侧没有更小元素。最直白的做法是两层循环外层固定i内层从i1扫到末尾。数据量小的时候完全没问题但一旦n到10^5这个量级O(n^2)就明显扛不住了。我最早刷这道题时就是先写暴力的结果被超时教育了一通。暴力的瓶颈在于每统计一个i都要重新扫描右侧段完全没有把已经有的大小关系复用起来。这道题真正考的是怎么在一次排序过程中顺便把“每个元素右侧有多少个比它小”这件事算完。这里要理解一个关键点它和“逆序对总数”不一样。逆序对的定义是i j且nums[i] nums[j]我们只需要统计有多少对这样的(i, j)。而本题要的是“每个i作为逆序对中左边那一个元素时它自己贡献了多少对”。也就是说逆序对总数是所有i的答案之和但题目要求把总数拆回到每个i头上。这个拆分的需求决定了我们不能只维护一个全局计数器而是要对每个原下标单独累加。如果你只是会写“求逆序对总数”的归并排序那很容易在这道题上翻车因为计数位置和累加方式都变了。后面我会专门讲这个差异。2. 归并排序为什么能顺手解决这道题2.1 每个“右小元素”关系都只会被处理一次分治解法的核心在于归并排序的递归结构。假设当前正在处理数组区间[l, r)把它分成左半[l, mid)和右半[mid, r)。对任意一对满足i j的下标它们要么同时落在左半要么同时落在右半要么一个在左半、一个在右半。前两种情况会在更深的递归层被继续处理后一种情况则正是在当前这一层合并时被统计。也就是说任何一个“右侧小于当前元素”的计数关系都会在某个归并层被恰好处理一次当且仅当发生计数的那两个元素在当前区间的左右两侧。这是归并排序能解决这类问题的天然前提。左右两侧各自排序完成后左半和右半内部的有序性已经不重要了重要的是两个子数组在合并时依然保持着原始数组的相对顺序左半的所有元素在原始顺序上都位于右半所有元素之前。2.2 合并时右侧元素比左侧元素先“出队”就是答案合并两个有序数组的标准操作是用两个指针i和j分别指向左半和右半每次把较小的那个放进临时数组。这里我们需要稍微修改一下计数逻辑。当nums[i] nums[j]时我们把左半当前元素放进临时数组。这时候右半指针j已经移到了某个位置j - mid就是右半中已经被放进临时数组的元素个数。由于右半是有序的而且内部元素是按照“当前右半元素小于左半当前元素”这一条件逐个放出来的所以这j - mid个元素全部是严格小于当前左半元素的值。它们又都来自右半也就是在当前元素原始位置的右侧。于是答案就清清楚楚了当左半元素nums[i]被放入临时数组时ans[当前元素的原始下标] j - mid。反过来如果nums[i] nums[j]说明右半当前元素更小我们直接把它放到临时数组里不需要对任何答案数组累加。因为它本身是右半元素它的“右侧更小元素”要在递归中或者更靠右的子数组中去统计而不是在当前这一层由左半来贡献。这里有个细节合并操作最终会把当前区间排成有序但这并不影响原始下标。我们只需要在递归过程中始终记录每个元素原本属于哪个位置就能把统计结果准确写回到ans的对应位置上。2.3 相等元素必须“左先出”否则会把等于也算成小于这个点特别容易踩。比较条件要用也就是左半元素小于等于右半元素时优先移动左半指针。为什么要这样因为题目要求的是“严格小于”而右半指针j - mid统计的是“已经被拿出来的右半元素个数”。如果两个值相等而你在合并时先把右半那个相等的元素拿出来等左半元素再出队时就会把这个相等的元素也算进“更小元素”里答案就变大了。最简单的验证是[5,5,5]正确答案是[0,0,0]。如果合并时采用if (left right)才取左半元素那么在第一次合并时右半的 5 会先被取走等左半的 5 再被取走时j - mid已经等于 1于是会错误地统计出 1 个“更小元素”。我的建议是先把这一条写在代码旁边“相等时取左边是为了保证不把相等元素计入严格更小。”3. 可复现的实现带原下标的归并排序3.1 数据结构设计因为归并排序会不断改变元素在数组中的位置我们不能只存数值否则排序结束后不知道这个值原本对应哪个位置。我习惯用一个pairint, int来存储first存数值second存原始下标。class Solution { public: vectorint countSmaller(vectorint nums) { int n nums.size(); vectorpairint, int a(n), tmp(n); for (int i 0; i n; i) { a[i] {nums[i], i}; } vectorint ans(n, 0); auto mergeSort [](auto self, int l, int r) - void { if (r - l 1) return; int mid l (r - l) / 2; self(self, l, mid); self(self, mid, r); int i l; int j mid; int k l; while (i mid j r) { if (a[i].first a[j].first) { ans[a[i].second] j - mid; tmp[k] a[i]; } else { tmp[k] a[j]; } } while (i mid) { ans[a[i].second] j - mid; tmp[k] a[i]; } while (j r) { tmp[k] a[j]; } for (int p l; p r; p) { a[p] tmp[p]; } }; mergeSort(mergeSort, 0, n); return ans; } };这段代码是典型的半开区间写法[l, r)表示当前要处理的区间左半是[l, mid)右半是[mid, r)。递归的终止条件是区间内元素数量小于等于 1这时候不需要排序也不需要统计。3.2 两个while循环不能少第一次while循环结束后只会有两种情况要么左半元素已经全部处理完要么右半元素已经全部处理完。如果是右半全部处理完而左半还剩下一部分元素那说明这些剩余左半元素是当前区间里最大的那部分右半的每一个元素都已经在它们之前被放进临时数组。因此当它们一个一个出队时都需要把右半的全部元素数量r - mid加到它们的答案里。这正是第二个while循环做的事情while (i mid) { ans[a[i].second] j - mid; tmp[k] a[i]; }有些版本会把这段写成固定的 r - mid逻辑上也是一样的因为此时j r。但为了和前面的j - mid保持一致性我更喜欢直接写j - mid一眼就能看出“右半已经出队的数量”。第三个while只是把剩下的右半元素搬运进临时数组这部分不再产生统计。最后把临时数组拷贝回a当前区间就排好序了。3.3 时间与空间复杂度每一层归并都是对整个区间的一次线性扫描递归深度是O(log n)所以时间复杂度是O(n log n)。空间上需要一个和原数组等大的临时数组以及一个答案数组总共O(n)。递归栈深度是O(log n)对n 10^5来说完全不是问题。对比暴力解法的O(n^2)归并排序版本的好处不仅在于复杂度降低更在于它没有引入值域相关的约束。元素是负数、浮点数在部分语言场景下、还是大到10^9都不需要额外处理因为排序只依赖元素之间的相对大小。4. 避坑笔记与调试技巧4.1 相等元素处理不当这是第一大坑。前面已经提过条件必须写保证左半元素优先出队。为了加深印象我用一个小例子说明错误的样子输入正确结果错误写法产生的结果[5,5,5][0,0,0][0,1,2][2,2,1][1,1,0]结果会偏大[3,1,3][0,0,0]结果会偏大[3,1,3]这个例子尤其容易错下标 0 的 3 右侧只有 1 比它小下标 2 的 3 右侧没有元素。如果合并时把相等的右半 3 先取出下标 2 的 3 就会在下标 0 的 3 之前进入临时数组导致下标 0 的 3 统计出两个“更小元素”正确答案的 1 就变成 2 了。4.2 用错下标排序后的位置不是原位置另一个常见问题是在合并时写成了ans[i] j - mid或者用ans[k]来累加。这里的k是临时数组的写入位置它只是“排序后当前元素应该去的位置”和“这个元素在原始数组里的下标”完全是两回事。比如[5,2,6,1]合并完左半[5,2]后a里第二个位置放的是 5 吗不是是(2,1)和(5,0)。如果此时你用当前数组位置当作答案下标那统计的是 2 的个数还是 5 的个数完全取决于排序后的顺序结果必然错乱。所以务必在开始时就把原始下标存下来所有累加都用a[i].second。4.3 别把“求逆序对总数”的代码直接搬过来求逆序对总数的归并排序计数是在取出右半元素时进行的每取出一个右半元素说明左半还剩mid - i个元素都比它大于是把这mid - i加到一个全局变量上。本题则是每取出一个左半元素时把右半已经取出的数量j - mid加到这个左半元素对应的ans上。这两者的“时机”和“累加目标”完全不同场景什么时候计数计数加到哪里求逆序对总数右半元素放入临时数组时全局总数total本题左半元素放入临时数组时左半元素的原下标对应的ans我第一次写的时候就是从“求逆序对总数”的模板改的只改了累加位置却忘了把计数时机从右半元素移动到左半元素来结果[5,2,6,1]跑出来乱七八糟。这个差异值得你单独记一下。4.4 用表驱动调试依赖打印日志在递归代码里比较吃力我更喜欢直接在小规模用例上验证配合手写推导。下面几个用例对排查问题很有用输入输出说明[5,2,6,1][2,1,1,0]标准混合用例[1,2,3,4][0,0,0,0]严格递增任何元素右侧都更小[4,3,2,1][3,2,1,0]严格递减每个元素右侧都比它小[1,1,1,1][0,0,0,0]全部相等严格小于一个都没有[][]空数组递归边界要能正确处理调试时还可以只输出每次合并前的左半、右半以及mid再手工核一遍某几个元素的ans会比盯整个递归过程轻松很多。5. 从这题往外走一步5.1 树状数组和线段树怎么做如果面试允许换思路这道题最常见的替代方案是从右往左扫描配合树状数组。具体做法是对值域做离散化然后倒序遍历原数组。每遇到一个nums[i]先查询树状数组中小于nums[i]的元素个数再把这个值插入树状数组。因为扫描是从右往左的所以查询到的所有元素都天然位于i的右侧一次查询就是答案。树状数组写起来可能更短但它有一个前提值域必须能映射到1..k的连续整数并且你要么提前排序去重要么用动态开点的方式处理。而归并排序的分治版本完全不需要离散化。如果nums里出现超大整数、负数甚至结构体对象只要它们之间能比较大小分治版本就能跑。5.2 什么时候优先选分治版本我个人更推荐先掌握归并排序版本理由有三个。第一它不依赖值域省去离散化这一步逻辑的“主战场”只在合并排序本身。第二它直接体现了“每个计数关系归属于哪个左元素”的本质对理解逆序对问题有很大帮助。第三归并排序可以很方便地扩展到类似问题比如“右侧大于当前元素的个数”只需要把比较方向倒过来“左侧小于当前元素的个数”可以换一种扫描方式或者调整左右半的统计规则。树状数组更适合在线场景比如边插入数据边查询或者需要动态修改数值的题目。但就这道题而言分治解法和树状数组解法的时间复杂度同为O(n log n)没有本质差距。5.3 我的实操经验我自己的习惯是遇到这种“右小计数”题先写一个归并排序分治版本跑通再去写树状数组版本对照。写完分治版本后你会对“元素出队顺序”和“左右半已处理数量”非常敏感这时再看树状数组就会觉得它只是把统计的载体从合并过程换成了线段树/树状数组而已。另外一个小建议写归并排序时区间定义一定要从头到尾保持一致。我用的半开区间[l, r)其实就是 C STL 里begin和end的习惯递归左右子区间分别是[l, mid)和[mid, r)可以避免很多1/-1的边界错误。如果你也准备用类似写法建议把这段核心逻辑默写下来先用小样例验证一遍再提交到在线评测系统。这种分治统计题的出错点非常集中只要避开了“相等元素”和“原下标丢失”这两个坑基本就能一次写对。