写这道题之前我先说个事。第一次见到“计算右侧小于当前元素的个数”这个需求很多人第一反应是双重循环数一数右边有多少比自己小的数交上去一看数据规模好家伙数组长度十万O(n²)直接原地超时。这道题在力扣上是第315题后面挂着个“(7)”意思差不多就是“这题有七种主流解法”之类的调侃但真正面试里能稳定写出来的其实就那么两三种思路归并分治、树状数组、线段树。这篇我就从最容易上手的归并排序分治法讲起把这个题从暴力解到分治优化一层层拆开保证你看完自己能写出来也能跟面试官把原理讲明白。这道题说白了就是给你一个整数数组让你返回一个新数组新数组第 i 个位置的值等于原数组里第 i 个元素右边所有元素中、比它小的元素个数。举个例子输入[5,2,6,1]输出就是[2,1,1,0]因为 5 右边比它小的是 2 和 1一共 2 个2 右边比它小的是 1一共 1 个6 右边比它小的是 1一共 1 个1 右边没有比它小的所以是 0。是不是很简单简单是简单但你要在 O(nlogn) 时间内算出来就得动点脑子了。这篇文章适合谁看准备算法面试的、刷题刚刷到归并排序想找练习题的、还有对“分治”这个概念停留在“二分查找”层面想再深入一层的朋友。我会把归并排序如何统计逆序对的思路迁移过来讲透“排序过程中顺带统计”这个核心技巧然后给出一份能直接提交的 C 代码再带你手动跑一遍全过程最后把常见网上报错的原因也梳理一遍。1. 问题到底在问什么暴力解与它的天花板1.1 最直观的解法为什么扛不住大数据量先看最直白的想法。遍历数组每个元素再嵌套一层循环从它右边第一个元素开始数遇到比自己小的就加一。代码非常简单我闭着眼睛都能写vectorint countSmallerBrute(vectorint nums) { int n nums.size(); vectorint ans(n, 0); for (int i 0; i n; i) { int cnt 0; for (int j i 1; j n; j) { if (nums[j] nums[i]) cnt; } ans[i] cnt; } return ans; }这个解法的时间复杂度是 O(n²)背后的逻辑就是暴力枚举所有“右侧元素”这个组合。n 等于几百、几千的时候毫无压力可一旦 n 到了十万内层循环总共要跑大约五十亿次比较在任何在线评测系统里都是稳超时的。面试时你写这个答案面试官大概率会点点头然后追问一句“还能优化吗”这时候你就得拿出点真功夫了。1.2 分治思想的直觉排序为什么能帮上忙先想一个问题如果数组是排好序的统计右边小于当前元素的个数是不是就简单了未必因为升序之后右边全是比自己大的答案全是 0这反而没有利用价值。但如果我们把一个数组切开左右两边分别变得有序那么在合并的过程中就存在一个可以利用的规律当一个左半部分的元素 x和右半部分的某个元素 y 做比较时一旦发现 y 比 x 小那么 y 之后的所有右半部分元素是不是一定也都比 x 小不一定因为右侧是有序的如果从某个位置开始右边的元素都比 y 大那结论就不成立。但如果右边是升序排列的而且我们是在归并的过程中从左到右依次比较两个有序段那情况就完全不同了我们可以精确记录“右侧已经有多少个元素比当前左侧元素小”。这就是“分治”里最经典的一类应用把统计问题转化成排序过程中的计数问题。本质上是借用了归并排序“部分有序”的中间状态用较小的代价得到全局信息。有个生活化的类比你在食堂排队想知道队伍里有多少人比自己矮。暴力法是你从队首跑到队尾挨个看分治法是先把队伍按高矮分成两排站好你只需要在合并两排时每看到一个比你矮的人就记一下而这个“看到”的过程正好就是归并排序的合并过程。省掉了大量重复比较。1.3 为什么是归并排序而不是快速排序或堆排序这里有个关键点归并排序是稳定排序而且在合并过程中两个子数组的相对顺序始终被保留。我们统计“右侧小于当前元素的个数”时必须区分元素原来的左右位置不能因为排序把左右关系弄丢。归并排序在分割阶段天然把数组分成左右两半合并阶段又能保持各自内部的相对位置所以它非常适合这种“跨左右区间”的计数。快速排序虽然也能分治但它的划分是基于基准值的元素在划分过程中会穿过左右边界不好维护右侧关系堆排序压根没有分治结构更不用提。所以这道题选归并排序不是巧合是它稳定加归并这两个特性刚好卡在这个问题的命门上。2. 归并解法核心设计什么时候计数、怎么计数2.1 核心思路在“合并”这个动作里顺手统计常规归并排序的合并函数做的事情是把两个已经有序的子数组按大小顺序逐个取出来放到一个临时数组里最后覆盖回原数组。我们要在“逐个取出来”的这个环节里插入统计逻辑。具体来说左边准备取出一个元素nums[i]放入临时数组的瞬间右边已经取出了多少个元素这些已经取出的右侧元素全都是比nums[i]小的因为右边是有序的先取出的一定是更小的所以nums[i]右侧比它小的元素数量至少要加上“右半部分已取出的元素个数”。那右边一直没取元素呢那右边当前指针指向的元素nums[j]比nums[i]大说明右半部分从nums[j]开始往后的所有元素都不比nums[i]小此时右边已取出的数量就是一个准确的计数。如果右边已经取出了若干个那这若干个是经过比较后确认小于nums[i]的数量就是准确的。所以计数时机放在“左边元素被放入临时数组”时。这个时机找得妙它保证了右边已取出的元素数量和“比当前左侧元素小的右侧元素数量”是严格相等的不多不少。2.2 为什么需要额外维护原始下标直接对原数组排序会丢掉元素原来的位置信息。比如[5,2,6,1]归并之后变成[1,2,5,6]你根本不知道答案应该填回哪个原始位置。解决办法是维护一个下标数组idx排序过程中原数组的值和对应的下标一起移动。排序结束后nums是排好序的idx是对应的原始下标。对nums[i]求出的计数就累加到ans[idx[i]]上。这个技巧在处理“排序后仍然要知道原始位置”的问题时非常通用比如后面讲到的树状数组解法、离线查询问题都会用到。2.3 等号怎么处理取小于还是小于等于归并排序合并时经常会遇到nums[i] nums[j]的情况。这时应该把左边元素放进临时数组还是把右边元素放进去对普通排序来说为了保证稳定性应该把左边的先放进去对本题来说这个选择也正好是对的当两个值相等时右边的这个元素“等于”左边元素不算“小于”。所以我们应该取把左边的元素放进去同时计数右边已经取出的数量这些取出的元素显然都小于当前值不包含那个相等的元素。如果写成就会导致相等的右侧元素被错误计入答案这一点是新手最容易踩的坑。3. 完整实现与手动推演让代码跑明白3.1 一份可直接提交的 C 参考代码基于上面的思路写出的代码长这样class Solution { public: vectorint countSmaller(vectorint nums) { int n nums.size(); if (n 0) return {}; vectorint ans(n, 0); vectorint idx(n); iota(idx.begin(), idx.end(), 0); // idx[i] i记录原始下标 vectorint tmp(n), tmpIdx(n); // 归并临时数组 mergeSort(nums, idx, tmp, tmpIdx, ans, 0, n - 1); return ans; } private: void mergeSort(vectorint nums, vectorint idx, vectorint tmp, vectorint tmpIdx, vectorint ans, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(nums, idx, tmp, tmpIdx, ans, left, mid); mergeSort(nums, idx, tmp, tmpIdx, ans, mid 1, right); merge(nums, idx, tmp, tmpIdx, ans, left, mid, right); } void merge(vectorint nums, vectorint idx, vectorint tmp, vectorint tmpIdx, vectorint ans, int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (nums[i] nums[j]) { ans[idx[i]] j - mid - 1; // 右边已弹出且比 nums[i] 小的元素个数 tmp[k] nums[i]; tmpIdx[k] idx[i]; i; } else { tmp[k] nums[j]; tmpIdx[k] idx[j]; j; } k; } while (i mid) { // 左侧还剩元素此时右半全部弹出 ans[idx[i]] j - mid - 1; tmp[k] nums[i]; tmpIdx[k] idx[i]; i; k; } while (j right) { // 右侧还剩元素补到临时数组 tmp[k] nums[j]; tmpIdx[k] idx[j]; j; k; } for (int p left; p right; p) { // 写回原数组 nums[p] tmp[p]; idx[p] tmpIdx[p]; } } };这段代码里最有技术含量的就是ans[idx[i]] j - mid - 1这一行。j - mid - 1表示右半部分已经被取出的元素个数因为右半部分的起始下标是mid 1当前指针是j所以已取出数量就是j - (mid 1)也就是j - mid - 1。注意在第一个while循环结束后如果左侧还有剩余此时j已经指向right 1那么j - mid - 1就等于right - mid正好是右半部分全部元素的数量计数逻辑依然正确。3.2 用一个具体例子完整手推归并过程拿[5, 2, 6, 1]来跑一遍。初始时idx [0, 1, 2, 3]。第一层递归左半[5, 2]右半[6, 1]。先处理左半分成[5]和[2]。合并[5]和[2]5 2不成立右边2先弹出j指向结束位置左侧5弹出时j - mid - 1 2 - 0 - 1 1所以ans中原始下标 0 累计 1。这个 1 代表 5 右侧的 2 比它小。此时数组变成[2, 5]下标变成[1, 0]。再处理右半[6]和[1]合并后变成[1, 6]原始下标变成[3, 2]同时ans[2]累计 1因为 6 右侧的 1 比它小。现在进入第二层的合并合并[2, 5]和[1, 6]。i指向 2j指向 1。2 1不成立右侧 1 弹出j指向 6。接着比较2 6成立左侧 2 弹出此时j - mid - 1 3 - 1 - 1 1所以原始下标 1元素 2的答案累计 1确实右边只有 1 比它小。然后i指向 5比较5 6成立左侧 5 弹出计数同样为 1所以原始下标 0 的答案变成 1 1 2正好对应 5 右边有 2 和 1 两个比它小。最后 6 直接放回计数为 0。最终ans是[2, 1, 1, 0]完全正确。整个过程最有趣的一点是所有计数都是在元素“被放回正确位置”那一刻完成的不需要额外的比较开销。归并排序本来就要做这些比较我们只是把一个原本会被丢弃的信息捡起来用这就是“顺带统计”的本质。3.3 时间与空间复杂度到底是多少每一层归并都要遍历整个区间做合并归并树共有logn层每层总耗时 O(n)所以总时间复杂度严格是 O(nlogn)。空间上用了tmp和tmpIdx两个辅助数组各 O(n)递归栈深度是 O(logn)所以总空间复杂度 O(n)。相比暴力解 O(n²) 的时间这是一个质的飞跃也是面试时你能给出并且要能解释清楚的复杂度结论。需要注意一点如果数组里所有元素都一样比如[7,7,7,7]答案自然全是 0。用上述代码因为取的是所以相等时左侧元素先弹出而右侧相等的元素还没有弹出j - mid - 1 0不会误计数。这个边界情况我建议你拿到手之后第一时间测一下能避免很多隐性 bug。4. 常见错误与排查心得这些坑我都踩过4.1 计数时机误判在右半元素弹出时计数结果全乱很多人在想这道题的时候会自然联想到“求逆序对总数”的写法那种写法在nums[i] nums[j]时把mid - i 1累加进逆序对总数理由是右边当前元素比左边剩余元素都小。但本题要求的是“每个元素的右侧小于它的个数”不是“逆序对的总数”如果照搬统计总数的思路你会得到一堆数字但不知道应该塞到谁头上。如果你在nums[i] nums[j]这个分支里去更新ans[idx[i]]那是错的因为此时右侧只弹出了一个j而左侧当前元素和左侧剩余元素都能和这个j构成逆序关系你没法区分哪些属于谁。正确做法是把计数放在左侧元素弹出时用j - mid - 1一次性累计已经弹出的全部右半元素数量这样每个左侧元素拿到的都是自己的准确值。这个区分是整个题解的灵魂建议调试时打印每一步的i, j, j-mid-1来观察。4.2 下标数组忘了同步更新答案张冠李戴第一次写这道题的时候我犯过一个很蠢的错误只对nums做了归并排序idx数组没有跟着排序结果排序之后下标数组和数值数组错位了最终答案完全乱套。归并排序里数值和下标必须是一对“绑定关系”不管用临时数组还是交换元素都要保证“某个数值移动到哪里它的原始下标就跟着移动到哪里”。代码里我把idx[i]和nums[i]放进同一个if-else分支就是为了保证这个绑定关系永远不被破坏。一旦你把两个数组分开处理铁定出错。4.3 递归边界处理不当合并时越界或漏算归并排序的递归写法有个经典边界mid left (right - left) / 2左半区间是[left, mid]右半是[mid 1, right]。如果你对mid的上取整下取整没有把握容易在递归到长度为 2 时出现死循环或漏算。一个保险做法是当left right时直接返回这样长度为 1 或 0 的区间都不会进入无限递归。另外在合并时两个 while 循环的收尾逻辑要各自处理不要把右侧收尾和左侧收尾混在一起写否则在某个子区间为空时会出现下标越界。我建议你从[1,2]、[2,1]、[1,1]这三个最短用例开始测能在 5 分钟内定位到绝大多数边界问题。4.4 把答案数组初值设错或者漏掉空数组特判ans数组初始化大小必须是 n初值 0。但如果输入为空ans的大小就是 0直接返回空数组即可不要进入归并递归否则left0, right-1会直接越界。这段代码我加上了一行if (n 0) return {};算是经验之谈很多代码在正常用例都能跑一提交遇到空数组样例就崩。还有一个容易忽略的点iota函数需要#include numeric如果你把idx[i] i写成显式循环就没这个问题但在在线评测时提交带iota的代码需要确保头文件齐全。4.5 误把结果当成原数组下标的累积最后再说一个调试时会遇到的疑惑为什么ans的值不是从下标 0 到 n-1 顺序给出的因为归并过程中元素位置会不断变化ans的写入位置取决于idx[i]指向的原始下标所以最终的ans数组虽然下标顺序是 0 到 n-1但更新顺序是乱序的。打个比方这就像一场考试后你在批改过程中把每个学生的分数按学生学号记在登记表上而不是按座位号记最后交上去的登记表虽然学号顺序是连续的但你填写时的顺序是乱的。这个设计不是 bug而是分治计数法的必要手段。如果你在某个中间过程打印ans看到数字乱序更新不要慌等递归结束再看最终结果。5. 同题另解与分治思想的延伸这题的多种打开方式5.1 树状数组加离散化的逆向思路除了归并分治这题还有一种非常经典的解法从右往左遍历把每个值映射成桶的编号用树状数组维护每个值出现的次数查询当前桶左边有多少个桶非空那就是右侧小于当前元素的个数。举例说遍历到元素5时树状数组里存的是 5 右侧所有元素的出现次数查一下小于 5 的桶数量得到答案然后把 5 自己也塞进树状数组继续往左走。这个过程需要先对数组做离散化压缩值域因为原始值可能跨度很大不能直接开数组。这种解法的时间复杂度同样 O(nlogn)但空间和常数上可能比归并略优面试时可以当作对比方案讲。如果面试官追问“既然从右往左也行为什么归并解法要保留原始下标”你正好把两种思路的都解释清楚。树状数组的核心操作就两个单点增量更新前缀和查询。代码反而比归并更简单但理解门槛在离散化把所有出现的值排序去重然后用lower_bound把原值映射成排名。这个“排名即桶编号”的思想在很多题里都能复用。不过从“分治”这个主题出发我更推荐你先掌握归并写法因为分治思路能迁移到更多变体比如后面说的逆序对总数、区间最大元素位置等。5.2 同一个分治框架还能解决什么问题“统计右侧小于当前元素的个数”其实是“统计逆序对问题”的加强版。经典逆序对题目通常只要求输出总数比如一个数组[5,2,6,1]的逆序对总数为 3但不需要精确到每个元素。你在归并过程中只需把mid - i 1之类的公式累加到一个总数变量里就行不需要维护idx数组。换句话说掌握带答案数组的写法后你可以减配成总数版本面试时快速切换。分治框架还能解决另一个常见问题查找数组中最大元素的位置。方法很简单递归求左半最大元素的位置、右半最大元素的位置然后比较两者并返回更大的那个。这和归并排序的分治结构一模一样只是“合并”操作从排序变成了比较。很多初学者刷题时会忽略这种“同框架下不同语义”的联系导致我以为分治就是二分查找、就是排序其实分治的核心是“把大问题拆成同类子问题分别解决后合并结果”。统计右侧小于当前元素的个数、求最大元素位置、归并排序、逆序对这四个问题可以用同一棵递归树串起来这也是你可以向面试官展示的深度理解。再往深里说有一类动态规划优化技术叫“四边形不等式优化”它的分治解法也用了类似的哲学把状态转移切成两半决策点具有单调性利用分治来快速缩小每一层的转移范围。虽然这个题不需要 DP但如果你面试里遇到区间 DP 题目能提一句“这里的决策单调性可以用分治 DP 优化把 O(n²) 的转移降到 O(nlogn)”会很加分。不过千万不要硬扯要确保自己真的懂才提。5.3 动手实验改进代码观察计数行为读完上面代码后我强烈建议你亲手做一个小实验在merge函数里每执行一次ans[idx[i]] j - mid - 1就打印出当前左侧值、该值对应的原始下标、本次加上的数量、右侧已弹出数量。你会很直观地看到同一个原始下标在递归的不同层级会被累加多次因为每一层只会统计当前左右分区中“右侧小于它”的那部分元素。比如5这个元素在第一层合并时统计了右侧的2在第二层合并时统计了右侧半区里的1两次相加就是完整答案。这是分治思想最核心的体现每层只解决自己分区范围内的统计问题子问题合并后全局答案自然浮现。顺手说个测试技巧可以用随机数组做对拍。写一个暴力函数再写一个归并解法然后把随机生成的数值分别输入两个函数比较输出。对拍数据量可以开 1000 组、每组长度 200一般跑几十秒就能覆盖绝大多数边界情况能替你省下不知道多少调试时间。我当年刷题时对拍脚本帮我把这种细节型题的错误率从 30% 直接干到 0强烈推荐你养成这个习惯。6. 从写题到讲题怎么跟面试官说清楚这套方案很多同学能把代码写出来一让讲思路就卡壳。这道题如果面试官问“你来说说归并排序为什么能统计右侧小于当前元素的个数”你可以按这个顺序讲逻辑特别顺第一步先讲暴力思路主动说时间复杂度 O(n²) 不适用于大数据量。第二步转向分治思路强调归并排序合并时左右两个子数组各自有序左侧元素每次出列时右侧已经出列的元素个数就是右侧小于它的元素个数。第三步解释为什么需要idx数组因为排序打乱了原始位置必须用下标绑定的方式记录答案应该填到哪个位置。第四步讲边界处理尤其是等号场景和空数组。整个讲解控制在两三分钟内重点突出第二步和第三步。还有一个容易被面试官追问的细节为什么不用快速排序这个问题前面已经讲过快速排序虽然也是分治但划分过程会让元素跨越左右边界很难在排序过程中自然确定“某个元素右侧有哪些元素”而归并排序的左右分区边界是固定的天然契合。如果你能答出这一层面试官通常就会点点头把问题转到复杂度分析或者同类变体上。我个人在实际刷题过程中的体会是这题真正难的并不是看题解那一刻而是你能否在三天后完全不看代码的情况下手写出带idx数组的归并排序。建议你用我上面给的最短用例[5,2,6,1]先手推一遍递归展开和合并过程再在纸上默写代码写错了就看一眼关键行ans[idx[i]] j - mid - 1补完再推一遍。这个流程重复三次你就再也不会忘记这个技巧了。