LeetCode 315： 算右侧小于当前元素的个数（归并排序） —— 题解
👋 欢迎阅读
🔥愿旖旎· 个人主页
📘学习专栏：《算法专栏》《LangChain学习》《贪心算法》
🌄 钱塘江上潮信来，今日方知我是我
✨当前学习内容：《归并排序》
一.题目
315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
🎯 欢迎来到「计算右侧小于当前元素的个数」题解之旅！本文将带你从"数一数每个数右边有几个比它小的"这一直观场景出发，深入理解归并排序 + 下标同步的巧妙运用，并掌握如何在降序合并的瞬间把更小元素个数写回原下标来在 O(n log n) 内算出每个位置的答案。
在开始之前，建议你先：
了解题目背景：这是 LeetCode 315 题，给定整数数组
nums，返回数组count，其中count[i]是nums[i]右侧比它严格小的元素个数。本质上，暴力两两比较是 O(n²)，而归并排序合并两个有序段时，能一次性算出左段元素右侧有多少更小的，问题转化为分治过程中的批量计数。明确学习目标：掌握降序合并 + 计数时机，理解下标数组
index必须与数值数组同步的原因，并熟练处理相等元素（<=）与回填偏移等边界情况。准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如
nums = [5,2,6,1]输出[2,1,1,0]）。
本文将从问题转化、分治拆分、合并计数、下标同步到代码实现，层层递进。即使你对逆序类计数还不熟悉，我们也会从"右段已排好序，右段一个元素能一次性代表好几个更小的数"这一直觉出发，让你轻松抓住核心思想——边归并边记账，下标随身带。现在，让我们一起归并计数，算出每个位置右侧更小的个数吧！
二、算法分析
1. 问题分析（前置分析）
- 题目要求：返回
count，count[i]为nums[i]右侧严格小于它的元素个数。 - 关键约束：
n可达10⁵，暴力 O(n²) 会超时；要求严格小于（相等不算）；结果需按原始下标对应。 - 核心思路：归并排序升序合并时，两段各自有序；若左段当前元素更大，则右段剩余元素全部更小，可以一次性累加它们的个数，再把计数写回该元素的原下标。
2. 算法策略（归并排序 + 降序合并 + 同步下标）
核心步骤：
- 初始化：
index[i] = i（记录每个位置的元素来自原数组哪个下标），结果数组v清零。 - 递归拆分：取中点
mid = left + (right - left) / 2，分别处理[left, mid]与[mid+1, right]。 - 降序合并：
cur1指左段、cur2指右段，大者先写入tmp（nums[cur1] <= nums[cur2]时取右段）。 - 计数时机：当
nums[cur1] > nums[cur2]（取左段元素）时，右段剩余[cur2, right]全部更小，累加v[index[cur1]] += right - cur2 + 1。 - 同步搬运：每写一个值，同时写它的原下标到
tmpIndex（数值与下标必须成对移动）。 - 回填：
nums[k] = tmpNums[k - left]、index[k] = tmpIndex[k - left]。
📊 示例（nums = [5,2,6,1]，期望[2,1,1,0]）：
| 阶段 | 区间 | 比较 | 操作 | 结果更新 |
|---|---|---|---|---|
| 合并 | [0,1] | 5 vs 2 | 5 > 2，取左段5 | v[0] += 1 |
| 合并 | [2,3] | 6 vs 1 | 6 > 1，取左段6 | v[2] += 1 |
| 合并 | [0,3] | 5 vs 6 | 5 ≤ 6，取右段6 | 无 |
| 合并 | [0,3] | 5 vs 1 | 5 > 1，取左段5 | v[0] += 1（累计2） |
| 合并 | [0,3] | 2 vs 1 | 2 > 1，取左段2 | v[1] += 1 |
| 收尾 | — | — | 搬入1 | 无 |
三次计数后v = [2,1,1,0]✅，正好是每个元素右侧更小元素的个数。
3. 正确性说明
- 公式正确：右段为降序，
[cur2, right]中每个元素都≤nums[cur2]；若nums[cur1] > nums[cur2]，则它们全部严格小于nums[cur1]，个数恰为right - cur2 + 1。 - 计数时机正确：只有"取左段元素"时才可能发现"右段有更小的"；取右段元素时右段更大，不可能存在更小的，故不计数。
- 下标正确：每次搬运都数值与下标成对移动，
v[index[cur1]]精确写回该元素的原始位置，不会张冠李戴。 - 跨层不重复：每层只统计"左段元素 × 右段元素"之间的更小关系，段内部的关系在递归子层已统计，互不重叠。
📌 例子：为什么right - cur2 + 1恰好是更小个数
合并
[5,2]与[6,1]（右段降序）：取左段5时，右段剩余[1]全部更小 → 1 个；取左段2时，右段剩余仍是[1]→ 1 个。两个左段元素各自"看见"了自己右侧更小的元素，个数就是右段剩余长度，公式直接生效。
4. 实现细节
- 初始化：
tmpNums、tmpIndex为成员静态数组，容量需> n（n ≤ 10⁵，取500005足够）；index[i] = i、v.resize(n)。 - 边界防护：
if (left >= right) return;（单元素无更小元素）；mid = left + (right - left) / 2（防溢出）；回填时偏移必须减 left（tmpNums[k - left]），且nums与index两条都要回填。 - 复杂度：时间 O(n log n)（log n 层合并，每层总扫描 O(n)），空间 O(n)（两个静态数组 +
index/v）。 - 关键操作：
v[index[cur1]] += right - cur2 + 1;（写回原下标的计数）、tmpIndex[i++] = index[cur2++];（下标同步搬运）。
📌 例子：为什么必须同步维护index
nums = [1,5,2]：初次合并后[1,5]被整理为[5,1]，index[0]变成1（值 5 的原下标）。最终合并取到值5时，若写v[cur1]会记到v[0]（错），而v[index[cur1]] = v[1]才正确（值 5 在原始数组的下标是 1）；最终v = [0,1,0]✅——排序打乱了位置，答案却必须按原下标落位，这就是index存在的意义。
5. 返回值
- 返回
v：每个原始下标对应的右侧更小元素个数，对应题目"返回每个元素右侧小于它的元素个数数组"。
三.代码
class Solution { int tmpNums[500005]; // 临时数组：合并时存放数值 int tmpIndex[500005]; // 临时数组：合并时存放下标（与数值同步移动） vector<int> v; // 结果：v[i] = nums[i] 右侧严格小于它的元素个数 vector<int> index; // 当前位置的元素来自原数组的哪个下标 public: vector<int> countSmaller(vector<int>& nums) { int n = nums.size(); v.resize(n); index.resize(n); for (int i = 0; i < n; i++) { index[i] = i; // 初始时位置 i 的元素就来自原下标 i } mergeSort(nums, 0, n - 1); return v; } void mergeSort(vector<int>& nums, int left, int right) { // 1. 递归终止：单元素无“右侧更小元素” if (left >= right) { return; } // 2. 取中点，分别排序左右两段 int mid = left + (right - left) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); // 3. 降序合并：大者优先写入 tmp int cur1 = left; // 左段指针 int cur2 = mid + 1; // 右段指针 int i = 0; // tmp 写入位置 while (cur1 <= mid && cur2 <= right) { if (nums[cur1] <= nums[cur2]) { // 右段元素更大或相等：先取右段（相等不计入“更小”） tmpNums[i] = nums[cur2]; tmpIndex[i++] = index[cur2++]; } else { // 左段元素更大：右段剩余 [cur2, right] 全部比它小 v[index[cur1]] += right - cur2 + 1; tmpNums[i] = nums[cur1]; tmpIndex[i++] = index[cur1++]; } } // 4. 收尾：剩余元素与下标成对搬运 while (cur1 <= mid) { tmpNums[i] = nums[cur1]; tmpIndex[i++] = index[cur1++]; } while (cur2 <= right) { tmpNums[i] = nums[cur2]; tmpIndex[i++] = index[cur2++]; } // 5. 回填：数值与下标两条都要还原，tmp 从 0 写起故减去 left for (int k = left; k <= right; k++) { nums[k] = tmpNums[k - left]; index[k] = tmpIndex[k - left]; } } };四、易错点分析
难点1：这是降序合并，计数发生在"取左段"时
if (nums[cur1] <= nums[cur2]) { tmpNums[i] = nums[cur2]; // 取右段（大者先） } else { v[index[cur1]] += right - cur2 + 1; // 取左段时才计数 }与 LCR 170 的"升序合并 + 取右段计数"恰好镜像：本题要求"右侧更小"，所以让大者先出（降序），当左段元素更大时才说明右段剩余"全部更小"，此时计数right - cur2 + 1。若照搬 170 的升序写法，计数方向与公式全部对不上，结果错误。
难点2：index必须与nums全程同步
tmpNums[i] = nums[cur1]; tmpIndex[i++] = index[cur1++]; // 数值走一步，下标也走一步排序会打乱元素位置，但答案必须按原始下标落位。因此每次搬运、每个收尾、每次回填都要成对处理nums与index：漏搬下标、或回填只还原了nums，都会让v[index[...]]写到错误位置——"数值与下标是绑定的两条轨道"，这是本题区别于 170 题的最大特征。
难点3：取右段元素时绝不能计数
if (nums[cur1] <= nums[cur2]) { // 这里只有搬运，没有 v += ... }当右段元素更大（或相等）时，它右侧（右段内部）后续元素只会更小或相等，但它本身不是"比左段元素小"——左段元素右侧没有发生"更小"关系。若在这个分支也累加，就会把"更大的元素"误当成"更小的"计数，结果偏大。
难点4：<=让相等元素不计入（严格小于）
if (nums[cur1] <= nums[cur2])题目要求严格小于。nums[cur1] == nums[cur2]时用<=取右段，不累加，正确；若写成<，相等时会走else累加right - cur2 + 1，把相等的元素也算成"更小"，结果偏大。一个符号决定答案是否包含等号。
五、流程图
🎯 闭幕
🎉 恭喜你完成了「计算右侧小于当前元素的个数」问题的学习！
为了巩固知识并进一步拓展，建议你：
🚀 动手实践在 LeetCode 上提交代码，尝试不同的测试用例。
💡 深入思考
- 代码用
v[index[cur1]] += right - cur2 + 1。请问为什么不能写成v[cur1] += ...？用nums = [1,5,2]说明。 index数组在每次搬运和回填时都要同步。请问如果只还原nums、漏还原index会发生什么？- 右段元素被取出时不计数。请问如果在这个分支也累加会得到什么？它对应的是"更大"还是"更小"？
如果你觉得本文对你有所帮助，欢迎：
👍 点赞 / 收藏 👤 关注作者，获取更多题解 💬 留言交流你的疑问或优化思路
📌 深入思考答案
- 因为排序后元素位置已变，
cur1只是"当前数组位置"，不代表原始下标。[1,5,2]初次合并后值5位于位置 0 但原下标是 1，若写v[cur1]会记到v[0]；必须写v[index[cur1]] = v[1]才正确，最终得到[0,1,0]。 - 只还原
nums会让index仍停留在旧状态，与数值不再对应；后续合并时v[index[...]]会写到错误位置，结果整体错乱——数值与下标必须始终成对移动、成对回填。 - 右段元素被取出说明它更大或相等，其右侧后续元素即使更小，也与"左段元素右侧更小"无关；在此累加会把更大的元素误算成"更小个数"，
v偏大。
祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨