数组中的逆序对
难度：中等
描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围
对于 50%的数据, size≤104
对于 100%的数据,size≤105
数组中所有数字的值满足 0≤val≤109
举例
解题思路
因为我们在归并排序过程中会将数组划分成最小为1个元素的子数组，然后依次比较子数组的每个元素的大小，依次取出较小的一个合并成大的子数组。
//取中间 int mid = (left + right) / 2; //左右划分合并 merge(divide(left, mid, data, temp), divide(mid + 1, right, data, temp));
这里我们也可以用相同的方法划分，划分之后相邻一个元素的子数组就可以根据大小统计逆序对，而不断往上合并的时候，因为已经排好序了，我们逆序对可以往上累计。我们主要有以下三个阶段。
- step 1： 划分阶段：将待划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为1.
- step 2： 排序阶段：使用归并排序递归地处理子序列，同时统计逆序对，因为在归并排序中，我们会依次比较相邻两组子数组各个元素的大小，并累计遇到的逆序情况。而对排好序的两组，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。
- step 3： 合并阶段：将排好序的子序列合并，同时累加逆序对。
实现代码(java)
public class Solution { public int mod = 1000000007; public int mergeSort(int left, int right, int [] data, int [] temp){ //停止划分 if(left >= right) return 0; //取中间 int mid = (left + right) / 2; //左右划分合并 int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); //防止溢出 res %= mod; int i = left, j = mid + 1; for(int k = left; k <= right; k++) temp[k] = data[k]; for(int k = left; k <= right; k++){ if(i == mid + 1) data[k] = temp[j++]; else if(j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++]; //左边比右边大，答案增加 else{ data[k] = temp[j++]; // 统计逆序对 res += mid - i + 1; } } return res % mod; } public int InversePairs(int [] array) { int n = array.length; int[] res = new int[n]; return mergeSort(0, n - 1, array, res); } }
