今日题目链接: 数组中的逆序对
数组中的逆序对
难度：中等
描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围
对于 50%的数据, size≤104
对于 100%的数据,size≤105
数组中所有数字的值满足 0≤val≤109
举例
解题思路
因为我们在归并排序过程中会将数组划分成最小为1个元素的子数组，然后依次比较子数组的每个元素的大小，依次取出较小的一个合并成大的子数组。
代码语言：javascript复制//取中间
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)
代码语言：javascript复制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);
}
}
