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

数组中的逆序对

http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5

利用归并排序解题

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
};
全部评论

相关推荐

07-11 10:56
门头沟学院 Java
码客明:大胆的说自己能实习6个月就行
点赞 评论 收藏
分享
鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-11 11:29
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务