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

from re import S
#from re import S
#

#from pandas import test
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def __init__(self):
        self.count = 0
		
		#采用分治
    def _count(self,nums,start,end):
        if start >= end:
            return 
        mid = int((start+end)/2)
        #分组左右两个组，并按照大小排序
        left = nums[start:mid+1]
        right = nums[mid+1:end+1]
        left.sort()
        right.sort()
        i = 0
        j = 0
        while i<len(left) and j<len(right):
			#如果left数组中某一个元素x大于right中某一个，测说明left中x之后的元素都满足条件
            if left[i]>right[j]:
                self.count += (len(left)-i)
                j+=1
            else:
                i+=1
        self._count(nums,start,mid)
        self._count(nums,mid+1,end)

    def InversePairs(self , nums) -> int:
        self._count(nums,0,len(nums)-1)
        return self.count%1000000007