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

import java.util.*;


public class Solution {
    public int res = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        if(nums.length == 0||nums.length == 1){
            return 0;
        }
        int start = 0;
        int end = nums.length-1;
        mergeSort(nums,start,end);

        return res;
    }

    private void mergeSort(int[] nums, int start, int end) {
        // TODO
        if(start>=end){
            return;
        }
        int middle = (start+end)/2;
        mergeSort(nums,start,middle);
        mergeSort(nums,middle+1,end);
        merge(nums,start,middle,end);

        

    }

    private void merge(int[] nums, int start, int middle, int end) {
        // TODO
        int mod = 1000000007;
        int left = start;
        int right = middle+1;
        int[] tmp = new int[end-start+1];
        int index = 0;
        while(left<=middle&&right<=end){
            if(nums[right]<nums[left]){
                res += middle-left+1;
                res %= mod;
                tmp[index] = nums[right];
                index++;
                right++;
            }else{
                tmp[index] = nums[left];
                index++;
                left++;
            }
        }
        if(left<=middle){
            for(int i = left; i <= middle; i++){
                tmp[index++] = nums[i];
            }
        }else{
            for(int i = right; i <= end; i++){
                tmp[index++] = nums[i];
            }
        }
        for(int i = start; i <= end; i++){
            nums[i] = tmp[i-start];
        }
    }
}