一、题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
二、思路讲解
首先一眼看上去，二重循环暴力十分省事，然而时间复杂度为平方阶，超时。
public class Solution { public int reversePairs(int[] nums) { int count = 0 for (int i = 0; i <nums.length-1; i++) { for (int j = i + 1; j < len; j++) { if (nums[i] > nums[j]) { count++; } } } return count; } }
那么我们就思考更好的算法：
求逆序对类型的题目里，经常使用归并排序，因为在高级排序算法（归并排序、快速排序）里，能够明显看到阶段性排序效果的算法就是归并排序。
举个例子，例如在归并排序的最后一步：合并的过程中，有前后两部分（这两部分分别有序的）：
5 6 7 8 I 1 2 3 4
↑ ↑
i j
根据合并的思路，j指针所指小于i指针所指，会将4首先放回拷贝数组中。因为左半边数组也是有序的，所以1小于左半边的所有数字，因此逆序对个数可以直接加4。详解见力扣官方视频，讲得很好：数组中的逆序对
三、Java代码实现
其实只用在归并排序中加一行代码就行了。
代码中有几个细节问题：
int mid = left +(right - left) / 2; 避免left+right超过int范围；
归并排序中，合并时，如果nums[x]<=nums[y]的等号不取，排序将不稳定
class Solution { int count = 0; public int reversePairs(int[] nums) { this.count = 0; mergeSort(nums, 0, nums.length-1, new int[nums.length]); return count; } //传一个用于拷贝的temp数组，比每次都创建新数组的效率要更高 void mergeSort(int []nums, int i, int j, int []temp) { if(i >= j) { return; } int k = i + (j-i)/2; //取中间值，这样的写法避免i+j超过整型范围 mergeSort(nums, i, k, temp); mergeSort(nums, k+1, j, temp); merge(nums, i, k, j, temp); } void merge(int []nums, int i, int k, int j, int []temp) { int x = i; int y = k+1; int index = 0; while(x<=k && y<=j) { while(x<=k && nums[x]<=nums[y]) { //如果这里nums[x]<=nums[y]不写等号，归并排序将不稳定 temp[index++] = nums[x++]; } while(y<=j && nums[y]<nums[x]) { //注意这里不能写等号，因为逆序对是不能相等的 count += (k-x+1); //比归并排序多的一行 temp[index++] = nums[y++]; } } while(x<=k) { temp[index++] = nums[x++]; } while(y<=j) { temp[index++] = nums[y++]; } for(int m=i; m<=j; m++) { nums[m] = temp[m-i]; } } }
四、时空复杂度分析
时间复杂度： O(NlogN) 归并排序的时间复杂度
空间复杂度： O(N) 归并排序的空间复杂度，因为需要一个拷贝数组
