1.题目基本信息

1.1.题目描述

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

1.2.题目地址

https://leetcode.cn/problems/reverse-pairs/description

2.解题方法

2.1.解题思路

使用左闭右开的归并排序/使用线段树（暂未实现）

2.2.解题步骤

第一步，使用归并排序的模板对数组进行排序，注意，这里的排序要使用一个和原数组长度相同的sortedNums进行存储排序的内容，否则很容易超时（在这卡了很久）

第二步，在递归操作和合并排序子数组之间，遍历左子数组和右子数组，计算两个已经排序的子数组的重要翻转对数量，并加到最终结果中result

第三步，排序后，返回result即可

3.解题代码

Python代码

class Solution:
    # 归并排序(使用全局的sortedNums才不会超时)
    def reversePairs(self, nums: List[int]) -> int:
        self.result=0
        def mergeSort(sortedNums,left,right):
            if right-left<=1:
                for i in range(left,right):
                    sortedNums[i]=nums[i]
                return
            mid=(right-left)//2+left
            mergeSort(sortedNums,left,mid)
            mergeSort(sortedNums,mid,right)
            # 获取左右数组的翻转对的个数
            j=mid
            for i in range(left,mid):
                while j<right and not nums[i]>2*(nums[j]):
                    j+=1
                self.result+=right-j
            # 合并左右的排序数组
            i,j,k=0,0,0
            while k<right-left and i<mid-left and j<right-mid:
                if nums[left+i]>nums[mid+j]:
                    sortedNums[left+k]=nums[left+i]
                    i+=1
                else:
                    sortedNums[left+k]=nums[mid+j]
                    j+=1
                k+=1
            while i<mid-left:
                sortedNums[left+k]=nums[left+i]
                i+=1
                k+=1
            while j<right-mid:
                sortedNums[left+k]=nums[mid+j]
                j+=1
                k+=1
            for i in range(right-left):
                nums[i+left]=sortedNums[i+left]
        sortedNums=[0]*len(nums)
        mergeSort(sortedNums,0,len(nums))
        # print(nums)
        # print(self.result)
        return self.result

4.执行结果

归并排序的时间复杂度是O(nlogn)，但是可能比树状数组的性能要差一丢丢