个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创分治算法(7)_归并排序_计算右侧小于当前元素的个数
目录
温馨提示:
1. 题目链接
2. 题目描述
3. 解法
算法思路:
代码展示:
温馨提示:
这一道题的解法与求数组中的逆序对的解法是类似的, 但是这一道题要求的不是求总的个数, 而是要返回一个数组, 记录每一个元素的右边有多少个元素比自己小.所以这里将求逆序对的算法思路并不会详细详解, 如果还不是很了解的宝子们可以先去下面的博客查看:
分治算法(6)_归并排序_交易逆序对的总数-CSDN博客
1. 题目链接
OJ链接 : 计算右侧小于当前元素的个数
2. 题目描述
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1：
输入：nums = [5,2,6,1] 输出：[2,1,1,0] 解释： 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元素 (1) 1 的右侧有 0 个更小的元素
示例 2：
输入：nums = [-1] 输出：[0]
示例 3：
输入：nums = [-1,-1] 输出：[0,0]
3. 解法
算法思路:
这一道题的解法与求数组中的逆序对的解法是类似的，但是这⼀道题要求的不是求总的个数，而
是要返回一个数组，记录每一个元素的右边有多少个元素比自己小。
但是在我们归并排序的过程中，元素的下标是会跟着变化的，因此我们需要⼀个辅助数组，来将数
组元素和对应的下标绑定在⼀起归并，也就是再归并元素的时候，顺势将下标也转移到对应的位置
上。
由于我们要快速统计出某⼀个元素后面有多少个比它小的，因此我们可以利用求逆序对的第二种方法。
算法流程：
• 创建两个全局的数组：
vector<int> index：记录下标
vector<int> ret：记录结果
index 用来与原数组中对应位置的元素绑定，ret 用来记录每个位置统计出来的逆序对的个数。
• countSmaller() 主函数：
a.计算 nums 数组大小为 n；
b.初始化定义的两个全局的数组；
i.为两个数组开辟大小为 n 的空间
ii.index 初始化为数组下标；
iii.ret 初始化为 0
c.调用 mergeSort() 函数，并且返回 ret 结果数组。
• void mergeSort(vector<int>&nums, int left, int right) 函数：
函数设计：通过修改全局的数组 ret， 统计出每⼀个位置对应的逆序对的数量，并且排序；
无需返回值，因为直接对全局变量修改，当函数结束的时候，全局变量已经被修改成最后的结果。
• mergeSort() 函数流程：
a.定义递归出口：left >= right 时，直接返回；
b.划分区间：根据中点 mid，将区间划分为[left, mid] 和[mid + 1, right]；
c.统计左右两个区间逆序对的数量：
i.统计左边区间[left, mid] 中每个元素对应的逆序对的数量到 ret 数组中，并排序；
ii.统计右边区间[mid + 1, right] 中每个元素对应的逆序对的数量到 ret 数组中，并排序。
d.合并左右两个有序区间，并且统计出逆序对的数量：
i.创建两个大小为 right - left + 1 大小的辅助数组：
• numsTmp： 排序用的辅助数组；
• indexTmp：处理下标用的辅助数组。
ii.初始化遍历数组的指针：cur1 = left（遍历左半部分数组）cur2 = mid + 1（遍历右半边数
组）dest = 0（遍历辅助数组）curRet（记录合并时产⽣的逆序对的数量）；
iii.循环合并区间：
• 当 nums[cur1] <= nums[cur2] 时：
◦ 说明此时[mid + 1, cur2) 之间的元素都是小于 nums[cur1] 的，需要累加到 ret 数
组的 indext[cur1] 位置上（因为 index 存储的是元素对应位置在原数组中的下标）
◦ 归并排序：不仅要将数据放在对应的位置上，也要将数据对应的坐标也放在对应的位
置上，使数据与原始的下标绑定在⼀起移动。
• 当 nums[cur1] > nums[cur2] 时，无需统计，直接归并，注意 index 也要跟着归并。
iv.处理归并排序中剩余的元素；
• 当左边有剩余的时候，还需要统计逆序对的数量；
• 当右边还有剩余的时候，无需统计，直接归并。
v.将辅助数组的内容替换到原数组中去;
代码展示:
class Solution
{vector<int> ret;vector<int> index;//记录 nums 中当前元素的原始下标int tmpnums[100010];int tmpindex[100010];public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);//初始化index数组for(int i = 0; i < n; i++)index[i] = i;mergesort(nums, 0, n - 1);return ret;}void mergesort(vector<int>& nums, int left, int right){if(left >= right) return;//根据中间元素, 划分区间int mid = (left + right) >> 1;//[left, mid] [mid + 1, right]//2. 先处理左右两部分mergesort(nums, left, mid), mergesort(nums, mid + 1, right);//3. 处理一左一右的情况int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]) {tmpnums[i] = nums[cur2];tmpindex[i++] = index[cur2++];} else{ret[index[cur1]] += right - cur2 + 1;//重点tmpnums[i] = nums[cur1];tmpindex[i++] = index[cur1++];}}//处理排序过程while(cur1 <= mid) {tmpnums[i] = nums[cur1];tmpindex[i++] = index[cur1++];} while(cur2 <= right) {tmpnums[i] = nums[cur2];tmpindex[i++] = index[cur2++];} for(int j = left; j <= right; j++){nums[j] = tmpnums[j - left];index[j] = tmpindex[j - left];}}
}; 
