原题（来源Leetcode）
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入： [7,5,6,4] 输出： 5
限制：
0 <= 数组长度 <= 50000
解法
思想
暴力：双重循环检查，leetcode中超时
分治思想：使用归并排序的算法，每次给左右两个数组合并的时候，若右边数组中指向的元素小于左边数组指向的元素，则也小于左边数组指向的元素后面的任何一个元素（归并排序合并的时候左右两个数组都是有序的），则此时加上左边数组剩余的元素个数即可。
代码
归并排序大复习，这里提供两种写法：
下面是归并排序较简单的写法，就是每次将数组均分成两个子数组，分到不能再分的时候开始合并相邻的两个子数组。这种写法递归中会创建新数组并拷贝，因此时间成本会略高些。
class Solution {
int count;//全局变量计数
public int reversePairs(int[] nums) {
MergeSort(nums);
return count;
}
public int[] MergeSort(int[] array) {
if (array.length < 2) return array;
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(MergeSort(left), MergeSort(right));
}
public int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i == left.length)
result[index] = right[j++];
else if (j == right.length)
result[index] = left[i++];
else if (left[i] > right[j]){
count+=left.length-i;//加上左边数组剩余的元素个数
result[index] = right[j++];
}
else result[index] = left[i++];
}
return result;
}
}
下面是一种递归过程中不用创建数组的归并排序写法，只使用两个和原数组相同大小的数组来回交换数据（做对方的缓存），在局部上操作，时间成本会比上面创建数组的方法更低些，但是是一个量级的，在leetcode中能取得更好的成绩：
class Solution {
public int reversePairs(int[] nums) {
int[] temp = nums.clone();//创建一个和原数组相同大小的数组
return MergeSort(nums, temp, 0, nums.length - 1);
}
//[start,end]确定一个数组范围，即递归中要排序的范围，返回值为合并过程中的计数
private int MergeSort(int[] nums, int[] temp, int start, int end) {
if (start >= end) return 0;
int mid = (start + end)/2;
int left = MergeSort(temp, nums, start, mid);
int right = MergeSort(temp, nums, mid + 1, end);
int count = merge(nums, temp, start, mid+1, end);
return left + right + count;
}
//[left,right)和[right,end]确定数组的两部分，合并temp数组中的这两部分到nums数组
private int merge(int[] nums, int[] temp, int left, int right, int end) {
int index = left;
int leftSize = right;//因为直接使用left和right作为后面使用的双指针，这里保存right原位置作为left指针能移动到的最远处
int count = 0;//合并过程中计数
while (index <= end) {
if (left==leftSize) nums[index] = temp[right++];
else if (right==end+1) nums[index] = temp[left++];
else if (temp[left] > temp[right]) {
count += (leftSize - left);//加上左边部分剩余的元素个数
nums[index] = temp[right++];
} else nums[index] = temp[left++];
index++;
}
return count;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%89%91%e6%8c%87offer51-%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e9%80%86%e5%ba%8f%e5%af%b9/
