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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#本题用暴力法会导致超时的问题。根据官方的思路，确实可以做出来，不超时，也即是分而治之的思路
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self, nums: List[int]) -> int:
        # write code here
        # 先分再合 
        self.count = 0 
        def recur(l) :
            if len(l) > 2:
                mid = len(l) // 2
                lltmp = l[0:mid]
                lrtmp = l[mid:]
                recur(lltmp)
                recur(lrtmp)
                lltmp.sort()
                print(lltmp)
                lrtmp.sort()
                i = 0
                for num in lrtmp :
                    if lltmp[-1] < lrtmp[0] :
                        break
                    while i < len(lltmp) :
                        if lltmp[-1] < num :
                            break
                        if lltmp[i] > num :
                            self.count += len(lltmp) - i
                            break
                        i += 1
            elif len(l) == 2 :
                if l[0] > l[1] :
                    self.count += 1 
            else :
                return
        recur(nums)
        return self.count % 1000000007