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

class Solution:
    def merge_sort_and_count(self,arr):
        """
        归并排序并统计逆序对的数量
        Args:
            arr: 待排序的数组
        Returns:
            排序后的数组和逆序对的数量
        """
        if len(arr) <= 1:
            return arr, 0
    
        mid = len(arr) // 2
        left, left_count = self.merge_sort_and_count(arr[:mid])  # 对左半部分进行归并排序
        right, right_count = self.merge_sort_and_count(arr[mid:])  # 对右半部分进行归并排序
    
        merged, merge_count = self.merge_and_count(left, right)  # 归并左右两部分并统计逆序对数量
        total_count = left_count + right_count + merge_count  # 总逆序对数量
    
        return merged, total_count
    
    def merge_and_count(self, left, right):
        """
        合并左右两个有序数组并统计逆序对的数量
        Args:
            left: 左半部分有序数组
            right: 右半部分有序数组
        Returns:
            合并后的有序数组和逆序对的数量
        """
        merged = []
        count = 0  # 用于统计逆序对的数量
        i, j = 0, 0
    
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                count += len(left) - i  # 统计逆序对数量
    
        merged.extend(left[i:])
        merged.extend(right[j:])
    
        return merged, count
    
    def InversePairs(self , data: list[int]) -> int:
        """
        计算逆序对的数量，并对结果取模
        Args:
            nums: 输入的整数数组
        Returns:
            逆序对数量取模的结果
        """
        _, count = self.merge_sort_and_count(data)
        return count % 1000000007