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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
     public static int count=0;
     public static int mod = 1000000007;
    public int InversePairs (int[] nums) {
        // write code here
        mergeSort(nums,0,nums.length-1);
        return count;
    }
    public void mergeSort(int[] nums,int l,int r){
        if(l==r) 
            return;
        int mid =(r-l)/2+l;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }
    public void merge(int[] nums,int l,int mid ,int r){
        int a = l;
        int b =mid+1;
        int k=0;
        int[] temp = new int[r-l+1];
        while(a<=mid&&b<=r){
            if(nums[a]<=nums[b]){
                temp[k++]=nums[a++];
            }else{
                //逆序对精髓
                //当右边的序列元素小于前面的序列元素时，出现了逆序对，且长度是前面序列的剩余长度，
                //因为剩余长度都大于当前的后面序列元素
                count+=(mid-a+1);
                count%=mod;
                temp[k++] =nums[b++];
            }
        }
        while(a<=mid){
            temp[k++] = nums[a++];
        }
        while(b<=r){
            temp[k++] = nums[b++];
        }
        k=0;
        for(int i=l;i<=r;i++){
            nums[i] = temp[k++];
        }
    }
}