题目
题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
输入
描述
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例
1,2,3,4,5,6,7,0 结果是 7
思路
一看到这个题我就感觉似曾相识，知道需要使用归并排序的思想来做，却早已忘记了归并排序的思想到底是什么。。。于是特地整理了一遍，见博客归并排序算法。
在归并排序的归并步骤时，可以顺便统计逆序对的个数。
假设正在归并上面的数组，左侧的2，3，6，8和右侧的1，4，5，7已经排好序了，左侧和右侧内部都没有逆序对，而从左侧取一个数，从右侧取一个数，则有可能形成逆序对。
例如，开始左侧拿出2，右侧拿出1，可知2>1，形成了逆序对。此时逆序对只是加1吗？并不是，因为2右边的数都是大于2的，所以可以判断左边的数和右边的1可以形成4对逆序对（(2,1)、(3,1)、(6,1)、(8,1)）。
接下来比2和4，不会形成逆序对。再比3和4，不会形成逆序对。
当比较到6和4的时候，形成了逆序对，个数为2((6,4)、(8,4))。
归纳一下，也就是在归并的时候，如果右侧的元素小于左侧的元素，这个时候开始统计逆序对就行了，如果左侧的索引为i，左侧的末尾元素的索引为mid，逆序对个数就为mid-i+1。
这样并没有结束，前面的假设是左侧和右侧是有序的，事实上并不是，左侧和右侧也进行了归并的过程才能变得有序，而在归并过程中，也能计算出逆序对的个数。
所以：
总的逆序对的个数=左侧归并时求得的逆序对个数 + 右侧归并时求得的逆序对个数 + 对整体进行归并时的逆序对个数。
可能会怀疑这三种情况会有重复，但是并没有。左侧归并找到的逆序对相当于从左侧数组中取2个数，而整体归并的时候是分别从左右数组中取1个数，不可能发生重复！
代码
知道上面的思路后，可以很容易的将归并排序代码进行修改。
class Solution {
public:
int res;
int InversePairs(vector<int> data) {
vector<int> aux = data; //辅助空间
return mergeSort(data, aux);
}
int mergeSort(vector<int> &arr, vector<int> &aux)
{
int n = (int)arr.size();
return __mergeSort(arr, aux, 0, n-1);
}
// [l, r]
int __mergeSort(vector<int> &arr, vector<int> &aux, int l, int r){
if(l >= r)
return 0;
int mid = l + (r-l)/2;
int left = __mergeSort(arr, aux, l, mid) % 1000000007;
int right = __mergeSort(arr, aux, mid+1, r) % 1000000007;
return (left + right + __merge(arr, aux, l, mid, r) )% 1000000007;
}
int __merge(vector<int> &arr, vector<int> &aux, int l, int mid, int r) {
for( int i = l ; i <= r; i ++ )
aux[i] = arr[i];
int res = 0;
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j];
j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i];
i ++;
}
else if( aux[i] < aux[j] ) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i];
i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j];
j ++;
res += (mid-i+1);
res %= 1000000007;
}
}
return res;
}
};
总结
求逆序对是对归并排序思想的经典应用，很巧妙。求逆序对好像还有树状数组的方法，精力不够，掌握一种方法足够了。
