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

利用归并排序解题

function feng(data,x,y,sum){
    if(x<y){
        let k = parseInt(JSON.stringify((x+y)/2));
        feng(data,x,k,sum);
        feng(data,k+1,y,sum);
        hebing(data,x,k,y,sum);
    }
}
function hebing(data,x,k,y,sum){//中间值k属于左侧
    let i=x,j=k+1,len=0;
    while(i<=k&&j<=y){
        if(data[i]>data[j]){
            ans+=k-i+1;
            sum[len++]=data[j++];
        } else{
            sum[len++]=data[i++];
        }
    }
    while(i<=k){
        sum[len++]=data[i++];
    }
    while(j<=y){
        sum[len++]=data[j++];
    }
    for(let db=x;db<=y;++db){
        data[db]=sum[db-x];
    }
    ans=ans%1000000007;
}
function InversePairs(data)
{
    // write code here
    let sum = [];
    feng(data,0,data.length-1,sum);
    return ans%1000000007;
}
module.exports = {
    InversePairs : InversePairs
};