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

import java.util.*;

public class Solution {
    //array为最终合并后的数组，temp为用于合并的临时数组
    int[] array,temp;
    public int mod = 1000000007;
    public int mergeSort(int left,int right){
        if(left>=right){
            return 0;
        }
        int mid=(left+right)/2;
        //划分
        int res = mergeSort(left,mid) + mergeSort(mid+1,right);
        res%=mod;
        
        //i,j分别指向两个划分段，k作为合并后的段的指针
        int i=left,j=mid+1,k;
        //复制原始数据作为分段合并的工作区
        for(k=left;k<=right;++k){
            temp[k]=array[k];
        }
        //合并，计算逆序对
        for(k=left;k<=right;++k){
            if(i==mid+1){
                //前半段合并完成,只须将右半段剩余的并入
                array[k] = temp[j++];
            }else if(j==right+1 || temp[i]<=temp[j]){
                //后半段已全部合入则直接合入前半段对应的值，或者前者比后者小即为升序，不逆序就直接合入较小的
                array[k] = temp[i++];
            }else{
                //存在逆序，则说明i及之后的值都大于j所指的值记录后合入较小的即后半段的值
                res=(res + mid - i + 1)%mod;
                array[k]=temp[j++];
            }
        }
        return res%mod;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        int n = nums.length;
        array = nums;
        temp = new int [n];
        return mergeSort(0,n-1);
    }
}

采用归并思想

求逆序对相当于在归并排序的同时判断有多少逆序对，采用归并排序的原因是它是先递归划分段再合并的，而且每次合并都是两个有序数组，若存在逆序可以更快的判断对数而无需对前面那个大的值之后的数挨个判断。

具体细节见程序注释。