# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 #本题用暴力法会导致超时的问题。根据官方的思路,确实可以做出来,不超时,也即是分而治之的思路 # # @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