刷题记录：数组中的逆序对

我什么都不会，甚至官解都看不懂

代码如下：

class Solution:
    mod = 1000000007
    
    def InversePairs(self , data: List[int]) -> int:
        n = len(data)
        temp = [0 for i in range(n)]
        return self.mergeSort(0, n - 1, data, temp)
        
    
    def mergeSort(self, left: int, right: int, data: List[int], temp: List[int]) -> int:
        if left >= right:
            return 0
        
        mid = (left + right) // 2
        res = self.mergeSort(left, mid, data, temp) + self.mergeSort(mid + 1, right, data, temp)
        res %= self.mod
        
        i, j  = left, mid + 1
        for k in range(left, right + 1):
            temp[k] = data[k]
        for k in range(left, right + 1):
            if i == mid + 1:
                data[k] = temp[j]
                j += 1
            elif j == right + 1 or temp[i] <= temp[j]:
                data[k] = temp[i]
                i += 1
            else:
                data[k] = temp[j]
                j += 1
                res += mid - i + 1
        return res % self.mod

其中，temp 列表负责暂存排序后的两个数组

第二个 for 循环中的 if-else 语句负责控制数组的合并以及低位元素的大小比较

通过合并时的大小比较来确定每次合并时有多少逆序对
然后递归返回逆序对个数