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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 */
int InversePairs(int* nums, int numsLen ) {
    // write code here
    int temp[100005];
    return mergeSort(nums, temp, 0, numsLen - 1);
}

int merge(int* nums, int* temp, int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    int count = 0;
    while(i <= mid && j <= right) {
        if(nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            count = (count + (mid - i + 1)) % 1000000007;
        }
    }
    while(i <= mid) temp[k++] = nums[i++];
    while(j <= right) temp[k++] = nums[j++];
    for(int i = left; i <= right; i++) {
        nums[i] = temp[i];
    }
    return count;
}

int mergeSort(int* nums, int* temp, int left, int right) {
    if(left >= right) return 0;
    int mid = left + (right - left) / 2;
    int count = 0;
    count = (mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid + 1, right) + merge(nums, temp, left, mid, right)) % 1000000007;
    return count;
}