【题目】
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof
【思路】
引入归并排序的思想，每一轮归并排序，实际上就是在比较两个数的逆序数，递归进行归并，同时记录每次递归的逆序数，累加就是逆序数的总和。
【代码】
class Solution { int[] nums,temp; public int reversePairs(int[] nums) { this.nums= nums; temp = new int[nums.length]; return mergeSort(0,nums.length-1); } private int mergeSort(int l,int r){ if(r<=l) return 0; int m = (l+r)/2; int res = mergeSort(l,m) + mergeSort(m+1,r); int i = l,j = m+1; // 将原始数组备份 for(int k=l;k<=r;k++){ temp[k]= nums[k]; } for(int k =l;k<=r;k++){ // 如果i（左边分组已经指向右边起始点）=m+1，则右边的按顺序存入即可 if(i==m+1){ nums[k] = temp[j++]; // 如果j（右边分组已经指向右边终点）=r+1或当前左边指向的数小于右边，则左边按顺序存入即可 }else if(j==r+1||temp[i]<=temp[j]){ nums[k] = temp[i++]; //否则，发生逆序情况，逆序个数为左边数的个数（因为右边小于左边的一个数，代表小于左边那个数右边的所有数） 数量为m-i+1 }else{ nums[k] = temp[j++]; res +=m-i+1; } } return res; } }