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

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        return self.fun(data)%1000000007
        # write code here
    # 类似于快排和归并的分治策略
    # 取第一个数 所有比它大的 大的，存到大的里面；所有比它小的 存到小的里面
    # 同时，记录逆序的个数 （解释在代码中）
    # 之后 把所有比它大的部分 肯定都比比它小的部分大 同理 必然小的 后面不会比它大
    # 所以递归调用比它大的部分和比它小的部分
    
    # 递归调用，计算送进来的数组的逆序对的个数
    def fun(self,arr):
        # 递归退出的条件
        if len(arr)<=1:
            return 0
        big=[]
        small=[]
        
        # 比较点 相当于 快排的第一个值
        prev=arr[0]
        res=0
        for i in arr[1:]:
            # 以当前值为分界点，如果遇到的值比它大，不是逆序不处理
            if i>prev :
                big.append(i)
            # 如果数比它小，则是逆序，要统计 这个比它小的数后面 有多少个逆序的大的数
            # 53498(21)678   看2比5还小 所以对5来说是逆序的 对2来说肯定也是逆序 对5来说是逆序的是98 有两个 所以加上了2，同理1也加上了2
            else:
                small.append(i)
                res+=len(big)+1
            # 5349821678 big:(98678) small(3421) 传递参数 调用98678 和 3421这样每次处理的数据都像归并一样，复杂度越来越小
            # 思考：为什么分为big 和 small 可以继续呢？？
            # 因为在存入big和small之前，已经记录过 small中每一项 是big（大于5的部分）是逆序的个数，而小于（大于）5 的那些数还没有统计过
            # 因为计算的方法一样，所以此时递归调用 处理这两部分 最后结果相加就是答案
        return res+self.fun(big)+self.fun(small)