题解 | #数组中的逆序对#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 */
 #define MOD 1000000007
 long long numsort(int* nums , int* temp , int left , int mid , int right){
    long long count = 0;
    int i = left;
    int Hl = left;
    int Hr = mid + 1;
    while(Hl <= mid && Hr <= right){
        if(nums[Hl] <= nums[Hr]){
            temp[i++] = nums[Hl++];
        }
        else{
            temp[i++] = nums[Hr++];
            count = (count + (mid - Hl + 1))%MOD;
        }
    }
    while(Hl <= mid ) temp[i++] = nums[Hl++];
    while(Hr <= right) temp[i++] = nums[Hr++];
    for(int k = left; k <= right ; k++ ) nums[k] = temp[k];
    return count%MOD;
 }
long long merge(int* nums , int* temp , int left , int right){
    if(left >= right) return 0;
    int mid = left + (right - left)/2;
    long long inv_count = 0;
    inv_count = (inv_count + merge(nums, temp, left, mid)) % MOD;
    inv_count = (inv_count + merge(nums , temp , mid + 1 , right))%MOD;
    inv_count = (inv_count  + numsort(nums , temp , left , mid , right))%MOD;
    return inv_count ;
 }
 int InversePairs(int* nums, int numsLen ) {
    // write code here
    if(numsLen < 2) return 0;
    long long count = 0;
    int* temp = (int*)malloc(sizeof(int) * numsLen);
    count = merge(nums , temp , 0 , numsLen - 1);
    free(temp);
    return count%MOD;
}