题目：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5

题目的理解：

取每一个数与后面的每一个数比较，如果大于后面的数则计数加1. 遍历完成后返回计数。

from typing import List

class Solution:
    def reversePairs(self, nums: List[int]) -> int:

        def lessNums(num: int, afterNums: List[int]) -> int:
            afterNums.sort()
            numsLength = len(afterNums)

            middle = numsLength // 2
            while True:
                if middle == 0:
                    if num <= afterNums[middle]:
                        return 0
                if middle == numsLength - 1:
                    if num > afterNums[middle]:
                        return numsLength

                if num > afterNums[middle]:
                    if middle + 1 <= numsLength - 1:
                        if num <= afterNums[middle + 1]:
                            return middle + 1

                    middle = (numsLength + middle) // 2
                    continue

                if num <= afterNums[middle]:
                    if middle == 0:
                        return 1

                    middle //= 2
                    continue

        result = 0
        for index, num in enumerate(nums):
            if index > len(nums) - 2:
                break

            resultOne = lessNums(num, nums[(index + 1):])
            result += resultOne

        return result

用了二分法来提高效率，时间复杂度O(n! * log(n)), 计算超时了。

开始看题目吧 !_!

python实现

没实现。

想看最优解法移步此处

提交

权当学习了。

// END 数学才是这个世界的主宰