1. 题⽬链接：315.计算右侧⼩于当前元素的个数
2. 题⽬描述：
3. 解法（归并排序）：
算法思路：
这⼀道题的解法与求数组中的逆序对的解法是类似的，但是这⼀道题要求的不是求总的个数，⽽ 是要返回⼀个数组，记录每⼀个元素的右边有多少个元素⽐⾃⼰⼩。 但是在我们归并排序的过程中，元素的下标是会跟着变化的，因此我们需要⼀个辅助数组，来将数 组元素和对应的下标绑定在⼀起归并，也就是再归并元素的时候，顺势将下标也转移到对应的位置 上。 由于我们要快速统计出某⼀个元素后⾯有多少个⽐它⼩的，因此我们可以利⽤求逆序对的第⼆种⽅ 法。
算法流程：
• 创建两个全局的数组：
vector index：记录下标
vector ret：记录结果
index⽤来与原数组中对应位置的元素绑定，ret⽤来记录每个位置统计出来的逆序对的个数。
• countSmaller()主函数：
a. 计算nums数组的⼤⼩为n；
b. 初始化定义的两个全局的数组；
i. 为两个数组开辟⼤⼩为n的空间
ii. index初始化为数组下标；
iii. ret初始化为0
c. 调⽤mergeSort()函数，并且返回ret结果数组。
• void mergeSort(vector& 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]
◦ 说明此时[mid+1,cur2)之间的元素都是⼩于nums[cur1]的，需要累加到ret数 组的indext[cur1]位置上（因为index存储的是元素对应位置在原数组中的下标）
◦ 归并排序：不仅要将数据放在对应的位置上，也要将数据对应的坐标也放在对应的位 置上，使数据与原始的下标绑定在⼀起移动。
• 当nums[cur1]>nums[cur2]时，⽆需统计，直接归并，注意index也要跟着归并。
iv. 处理归并排序中剩余的元素；
• 当左边有剩余的时候，还需要统计逆序对的数量；
• 当右边还有剩余的时候，⽆需统计，直接归并。
v. 将辅助数组的内容替换到原数组中去；
C++算法代码：
class Solution
{
public:
vector<int>answer; //答案
vector<int>weizhi; //记录每个数的下标
int temp[100001]; //排序所需
int temp_wei[100001]; //下标更新所需
void mergesort(vector<int>& nums,int left,int right)
{
//只有一个元素时返回
if(left>=right)
{
return ;
}
//取中间值
int mid=(left+right)/2;
//分别处理左右
mergesort(nums,left,mid);
mergesort(nums,mid+1,right);
//处理左右两部分
int cur1=left,cur2=mid+1,i=0;
//降序
while(cur1<=mid&&cur2<=right)
{
if(nums[cur1]<=nums[cur2])
{
//赋与数据和位置
temp[i]=nums[cur2];
temp_wei[i++]=weizhi[cur2++];
}
else
{
//更新答案
answer[weizhi[cur1]]+=right-cur2+1;
//赋与数据和位置
temp[i]=nums[cur1];
temp_wei[i++]=weizhi[cur1++];
}
}
//处理剩余数据
while(cur1<=mid)
{
//赋与数据和位置
temp[i]=nums[cur1];
temp_wei[i++]=weizhi[cur1++];
}
while(cur2<=right)
{
//赋与数据和位置
temp[i]=nums[cur2];
temp_wei[i++]=weizhi[cur2++];
}
//更新原始数据
for(int i=left;i<=right;i++)
{
nums[i]=temp[i-left];
weizhi[i]=temp_wei[i-left];
}
}
vector<int> countSmaller(vector<int>& nums)
{
int n=nums.size(); //数组大小
//开空间
answer.resize(n);
weizhi.resize(n);
//初始化下标数组
for(int i=0;i<n;i++)
{
weizhi[i]=i;
}
//归并排序
mergesort(nums,0,n-1);
return answer;
}
};Java算法代码：
class Solution
{
int[] ret;
int[] index; // 标记 nums 中当前元素的原始下标
int[] tmpIndex;
int[] tmpNums;
public List<Integer> countSmaller(int[] nums)
{
int n = nums.length;
ret = new int[n];
index = new int[n];
tmpIndex = new int[n];
tmpNums = new int[n];
// 初始化 index 数组
for (int i = 0; i < n; i++)
index[i] = i;
mergeSort(nums, 0, n - 1);
List<Integer> l = new ArrayList<Integer>();
for (int x : ret)
l.add(x);
return l;
}
public void mergeSort(int[] nums, int left, int right)
{
if (left >= right) return;
// 1. 根据中间元素划分区间
int mid = (left + right) / 2;
// [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++];
}
}
// 4. 处理剩余的排序⼯作
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];
}
}
}