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

1, 将原数组排序，然后从小到大遍历排序数组，求这个数在原数组中的index，这个index就代表有多少个数字在该数的前面并且大于这个数.注意：每次计算后要在数组中除掉这个数。
2, 第一种方法超时，题解第二种解法，首先以第一个元素作为对照，比这个数大的进入大数组，比对照数小的进入小数组，此时记录大数组的个数加上1，用result累加，就是此刻和该数对比有多少个逆序，然后递归操作大数组和小数组中的元素，直到元素个数为<=1.

# 方法一
class Solution:
    def InversePairs(self, data):
        # write code here
        return self.solve(data) % 1000000007
    def solve(self, arr):
        if len(arr) <= 1:
            return 0
        pivot = arr[0]
        big, small = [], []
        res = 0
        for i in arr[1:]:
            if i > pivot:
                big.append(i)
            else:
                small.append(i)
                res += 1 + len(big)
        return res + self.solve(big) + self.solve(small)
        # write code here
s = Solution()
print(s.InversePairs([1, 2, 3, 4, 5, 6, 7, 0]))

# 方法二
class Solution:
    def InversePairs(self, data):
        data2 = sorted(data)
        count = 0
        for i in data2:
            count += data.index(i)
            data.remove(i)  # 此时计算一次后要删除该元素
        return count % 1000000007