(归并排序思想)leetcode困难315. 计算右侧小于当前元素的个数

给你一个整数数组 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.一个count数组用来计数每个元素的逆序数
2.一个vector>的数组，用来将给定数组中的元素与下标绑定，因为我们在进行递归排序的时候会把原顺序打乱

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

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

		for(int i=0;i 
2.将所有数字拆分开 
首先分析当前要做的事情，将一个数组分成两个数组，然后递归两次，一次从左边深入，一次从右边深入，最后将原数组清空，然后调用函数（功能为将分开的两个数组整合，并且计算每个元素的逆序数），出口是当数组的长度为一时，我们不能再将数组进行拆分
 
	void merge(vector > &pai,vector &count)
	{
		//出口
		if(pai.size()<2)
			return;
		//现在做的事情
		int mid=pai.size()/2;
		vector > tmp1;
		vector > tmp2;
		for(int i=0;i 
3.数组整合并且计算逆序数 
这里主要是为了实现将两个有序的数组，及逆行整合，从两个数组中的第一个元素进行比较，小的数字就排放在前面。
 
如何计算逆序数，这里也是这道题的难点
 
 当我们比较难想象的时候可以画图进行理解，数组中的每个元素都是以但他的值和它的原始下标组成，前面的步骤就是左边的和右边的数组是怎么排序好的，我们不用想，交给递归来完成就好了，右边的数组的下标均是右边的四个下标，已经计算完成，我们就不需要计算右边的逆序数，只需要计算左边的逆序数，向总的数组中插入左边的元素时，我们就++记录当前左边数组插入到了第几项，插入右边数组中的元素时，我们就j++来记录，右边数组插入时。不用计算逆序数。左边的数组是插入时，逆序数应该+j，因为有j个左边的数字排到了它的前面，但是原来的顺序是在他的的右边
 
结束比较后，左边和右边的数组中可能还剩下一些元素，直接将剩下的元素，依次进入到总的数组中即可，注意左边的数组中进入的时候，逆序数的计算要加上j
 
void merge2(vector > tmp1,vector > tmp2,
	vector > &pai,vector &count)
	{
		int i=0,j=0;
		
		while(i 
完整代码 
class Solution {
public:
	void merge2(vector > tmp1,vector > tmp2,
	vector > &pai,vector &count)
	{
		int i=0,j=0;
		
		while(i > &pai,vector &count)
	{
		//出口
		if(pai.size()<2)
			return;
		//现在做的事情
		int mid=pai.size()/2;
		vector > tmp1;
		vector > tmp2;
		for(int i=0;i countSmaller(vector& nums) {
		vector > pai;	//将数字与当前的下标绑定 
		vector count;		//用来计数每个数字的逆序数
		
		for(int i=0;i 
总结 
归并的思想并不难，属于分治的一类，将原问题分解成小的问题，最后将所有的子问题的解加起来就是原问题的解。
 这道题的难点在于，如果再归并的过程中计算每个元素的逆序数，将每个元素与原始下标绑定，将归并的思想用到这道题上