(归并排序思想)leetcode困难315. 计算右侧小于当前元素的个数_java给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该

题目

给你一个整数数组 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]

数据范围

1 <= nums.length <= 105
-104 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

解读题意，给定一个数组，计算数组中的每个元素的逆序数，就是当前元素的的右侧有几个数字比他小，当前元素的逆序数就是多少
暴力的方法很好想，用每一个元素和后续的所有元素进行比较，数组的长度为n，时间复杂度为O（n^2），数据范围中最大的情况是10的五次方，利用这种暴力的方法，最坏的情况下大概为10的十次方，我们判断超时的情况大概是超过10的八次方就会超时，所以这种方法肯定是超时的

解决的方案是按照归并排序的思维，将数组先全都分开，组合的时候，前面的元素向后移动就计算它移动的距离，直到最后数组变得整体有序，所有数字的逆序数也计算完成。归并排序时间复杂度为O（nlogn），最坏的情况是 10的五次方*log10的五次方，计算log的技巧：2的十次方大概是10的三次方，2的二十次方大概是10的六次方，2的三十次方大概是10的九次方，以此类推。所以log10的五次方，不超过20。

代码部分

1. 初始化

递归需要的参数
1.一个count数组用来计数每个元素的逆序数
2.一个vector<pair<int,int>>的数组，用来将给定数组中的元素与下标绑定，因为我们在进行递归排序的时候会把原顺序打乱

		vector<pair<int,int> > pai;	//将数字与当前的下标绑定 
		vector<int> count;		//用来计数每个数字的逆序数
1
2

接下来我们初始化这两个数组，count中的每个元素初始化为0，pai中的每个元素是原数组中的元素与当前的下角标绑定

		for(int i=0;i<nums.size();i++)		//初始化 
		{
   
			pai.push_back(make_pair(nums[i],i));
			count.push_back(0);
		}
1
2
3
4
5
6

2.将所有数字拆分开

首先分析当前要做的事情，将一个数组分成两个数组，然后递归两次，一次从左边深入，一次从右边深入，最后将原数组清空，然后调用函数（功能为将分开的两个数组整合，并且计算每个元素的逆序数），出口是当数组的长度为一时，我们不能再将数组进行拆分

	void merge(vector<pair<int,int> > &pai,vector<int> &count)
	{
   
		//出口
		if(pai.size()<2)
			return;
		//现在做的事情
		int mid=pai.size()/2;
		vector<pair<int,int> >
1
2
3
4
5
6
7
8