题解 | #比较版本号#
数组中的逆序对
http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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;
}
