题解 | NO.20#数组中的逆序对#3.9

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 */

int mod = 1000000007;

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;
}

int InversePairs(int* nums, int numsLen ) {
    int temp[numsLen];
    int res = mergeSort(0,numsLen - 1,nums,temp);
    return res;
}