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

数组中的逆序对

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

# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        # write code here
        def mergeSort(L,R):
            if L>=R:
                return 0
            m=L+(R-L)//2
            cnt=mergeSort(L,m)+mergeSort(m+1,R)
            i,j=L,m+1
            pos=L
            while i<=m and j<=R:
                if data[i] <= data[j]:
                    tmp[pos]=data[i]
                    i+=1
                else:
                    tmp[pos]=data[j]
                    j+=1
                    cnt+=(m-i+1)
                pos+=1
            for k in range(i,m+1):
                tmp[pos]=data[k]
                pos+=1
            for k in range(j,R+1):
                tmp[pos]=data[k]
                pos+=1
            data[L:R+1]=tmp[L:R+1]
            return cnt
        n=len(data)
        tmp=[0]*n
        res=mergeSort(0,n-1)
        return res%1000000007
全部评论

相关推荐

07-18 18:05
门头沟学院 Java
挂了&nbsp;正式批求捞
投递滴滴等公司10个岗位
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
Java大菜狗:纯纯招黑奴,一天还不到两百那么多要求,还不迟到早退,以为啥啊,给一点工资做一堆活,还以不拖欠员工工资为荣,这是什么值得骄傲的事情吗,纯纯***公司
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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