关于数据结构与算法:每日leetcodeJZ51-数组中的逆序对

在数组中的两个数字，如果后面一个数字大于前面的数字，则这两个数字组成一个逆序对。输出一个数组，求出这个数组中的逆序对的总数。

要求：空间复杂度 O(n)，工夫复杂度 O(nlogn)

 输出: [7,5,6,4]
返回值: 5

输出：[1,2,3,4,5,6,7,0]
返回值：7

输出：[1,2,3]
返回值：0

最简略的思路是暴力求解，遍历数组每个元素，而后挨个和之后的元素比拟。这种做法工夫复杂度是 O(n^2)。

最优思路是，利用归并排序的做法。
归并排序，将数组递归二分到子数组只有 1 个元素，而后向上排序合并。

只有左数组的某个元素，大于右数组的某个元素，那么左数组的该元素以及之后的所有元素，都能够和右数组的该元素造成逆序对。

因为下一层通过排序合并返回上一层后，上一层的左、右数组都是从小到大正序的，如果左数组的某个元素就比右数组的某个元素大，那么左数组的该元素前面的元素也必定比右数组的该元素大。

class Solution:
    # 内部定义一个变量，用来记录逆序对数量
    count = 0

    def InversePairs(self, data):

        def mergeSort(nums):
            n = len(nums)
            # 归并排序 递归完结条件 分到子数组长度为 1 不可分时递归完结
            if n==1:
                return nums

            # 以后数组的两头地位
            mid = n//2
            # 左数组向下递归持续二分
            left = mergeSort(nums[:mid])
            # 右数组向下递归持续二分
            right = mergeSort(nums[mid:])

            # 定义两个指针: l、r，初始时别离指向左数组、右数组的开始
            l = r = 0
            # 定义一个变量，保留排序合并后的后果
            tmp = []
            # 当左、右两个数组 都没有遍历完
            while l<=len(left)-1 and r<=len(right)-1:
                # 如果左数组以后元素 <= 右数组以后元素
                # 则没有逆序对，左数组元素退出到排序后果中，l 指针挪动
                if left[l] <= right[r]:
                    tmp.append(left[l])
                    l+=1
                # 如果左数组以后元素 > 右数组以后元素
                # 则左数组以后元素 以及 前面的所有元素，都大于右数组以后元素
                # 都能够造成逆序对，count+ 这部分元素的数量
                # 右数组以后元素退出到排序后果中，r 指针挪动
                else:
                    tmp.append(right[r])
                    self.count+=len(left[l:])
                    r+=1
            while l<=len(left)-1:
                tmp.append(left[l])
                l+=1
            while r<=len(right)-1:
                tmp.append(right[r])
                r+=1
            return tmp

        mergeSort(data)
        return self.count

题目

思路