面试题51. 数组中的逆序对

面试题51. 数组中的逆序对

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

输入: [7,5,6,4]
输出: 5

两次遍历数组暴力解（超时）

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        cnt = 0
        n = len(nums)
        for x in range(n):
            for y in range(x,n):
                if nums[x] > nums[y]:
                    cnt += 1
        return cnt

归并排序

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0
        
        M = n // 2
        L = nums[:M]
        R = nums[M:]
        result = self.reversePairs(L) + self.reversePairs(R)
        
        # union left and right
        L.sort()
        R.sort()
        index = 0
        for j in range(len(R)):
            while index < len(L) and L[index] <= R[j]:
                index += 1
            else:
                result += (len(L) - index)
        return result

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

        def mergeSort(l = 0, r=len(nums)):
            if r - l > 1:
                mid = (l + r)//2

                mergeSort(l, mid)
                mergeSort(mid, r)

                i, j, tmp = l, mid, []
                while i < mid and j < r:
                    if nums[i] <= nums[j]:
                        tmp.append(nums[i])
                        i += 1
                    else:
                        tmp.append(nums[j])
                        j += 1
                        self.cnt += mid - i
                tmp.extend(nums[i:mid] if i<mid else nums[j:r])
                nums[l:r] = tmp

        self.cnt = 0
        mergeSort()
        return self.cnt