在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围：对于 50%50% 的数据, size≤10^4
对于100% 的数据, size≤ 10^5
数组中所有数字的值满足 0≤val≤1000000
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
输入描述：
题目保证输入的数组中没有的相同的数字
# 示例1
输入：[1,2,3,4,5,6,7,0]
返回值：7
# 示例2
输入：[1,2,3]
返回值：0
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param data int整型一维数组
* @param dataLen int data数组长度
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
static unsigned int count = 0;
void merge(int *arr, int lo, int mid, int hi);
void mergeSort(int *arr,int lo, int hi)
{
if(lo == hi) return;
int mid = (hi +lo) >> 1;
mergeSort(arr, lo, mid);
mergeSort(arr ,mid +1, hi);
merge(arr,lo, mid, hi);
}
void merge(int *arr,int lo, int mid, int hi)
{
int *B = (int*)malloc((mid - lo +1) * sizeof(int));
int i,j,k;
for(i = lo, j = 0; i <= mid; i++)
{
*(B + (j++)) = *(arr + i);
}
for(i = 0, k = lo, j = mid + 1;i <= mid - lo;)
{
if(*(B + i) > *(arr + j) && j <= hi)
{
count = count +(mid - lo - i + 1);
*(arr + (k ++)) = *(arr + (j ++));
}
else
{
*(arr + (k ++)) = *(B + (i ++));
}
//*(arr + (k ++)) = *(B + i) < *(arr + j) || j > hi ? *(B + (i ++)) : *(arr + (j ++));
}
free(B);
count = count % 1000000007;
}
int InversePairs(int* data, int dataLen ) {
mergeSort(data, 0, dataLen - 1);
return count;
}
