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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param data int整型一维数组
# @return int整型
#
class Solution:
    def InversePairs(self, data: list[int]) -> int:
        # write code here
        print(data)

        def megre_sort(L, R):
            if L >= R:
                return 0


            #求中间值
            mid = L + (R - L) // 2

            #求数组的左半部分和右半部分
            cnt = megre_sort(L, mid) + megre_sort(mid + 1, R)
            i = L
            j = mid + 1
            pos = L
            while i <= mid and j <= R:
                if data[i] < data[j]:
                    tmp[pos] = data[i]
                    i += 1

                else:
                    tmp[pos] = data[j]
                    cnt += mid - i + 1
                    j += 1
                pos += 1

            #如果未排序完，将剩下的没排序的数组排序
            for k in range(i, mid + 1):
                tmp[pos] = data[k]
                pos += 1

            for k in range(j, R + 1):
                tmp[pos] = data[k]
                pos += 1

            #拷贝tmp到data数组
            data[L : R + 1] = tmp[L : R + 1]
            return cnt

        n = len(data)
        tmp = [0] * n
        return megre_sort(0, n - 1) % 1000000007


# combine
# left= 1 2 3 4

# right = 5 6 7 0


# left = 12
# right= 3 4


# left=1
# right=2


# data = list(input().split())
# print()