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

数组中的逆序对

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

from re import template
from heapq import merge
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    mod = 1000000007
    total = 0
    #归并实现
    def merge(self, li, low, mid, high):
        i,j = low,mid+1
        temp = []
        sum = 0
        #两边都有数
        while i<=mid and j<=high: 
            if li[i] < li[j]:
                temp.append(li[i])
                sum += (len(temp) - (i-low+1)) #i-low+1是当前的左列表入列个数
                i += 1
            else:
                temp.append(li[j])
                j += 1
        print(sum)
        #两边都没了
        while i<= mid:
            temp.append(li[i])
            sum += (len(temp) - (i-low+1))
            i += 1
            
        while j<= high:
            temp.append(li[j])
            j += 1
        li[low:high+1] = temp
        return sum

    #递归实现排序与计数
    def mergesort(self,li,low,high):
        if low < high:#至少两个元素
            mid = (low+high)//2
            self.mergesort(li,low,mid)
            self.mergesort(li,mid+1,high)#排序
            self.total += self.merge(li,low,mid,high)
            self.total %= self.mod

    def InversePairs(self, nums: List[int]):
        n = len(nums)
        self.mergesort(nums,0,n-1)
        return self.total
        
        

直接做归并排序,在归并的时候同时计数

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 17:10
点赞 评论 收藏
分享
来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
asdasdasda...:19岁,不容易啊可能升个本会好点,现在学历歧视太严重了
点赞 评论 收藏
分享
牛客84809583...:举报了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 12:23
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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