Leetcode 每日一题——493. 翻转对

493. 翻转对

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

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

该题类似于逆序对个数的查找，使用归并排序进行求解，具体代码如下：

class Solution {
public:
    int reversePairsRecursive(vector<int>& nums,int left, int right)
    {
        if (left==right) return 0;
        int res=0;
        int mid=(left+right)/2;
        res+=reversePairsRecursive(nums,left,mid);
        res+=reversePairsRecursive(nums,mid+1,right);
        
        int i=left;
        int j=mid+1;
        while(i<=mid)
        {
            while(j<=right && (long long)nums[i]>2*(long long)nums[j]) j++;
            res+=(j-mid-1);
            i++;
        }
        vector<int> sorted(right-left+1);
        int pleft=left;
        int prigt=mid+1;
        int psort=0;
        while(pleft<=mid || prigt<=right)
        {
            if(pleft>mid)
            {
                sorted[psort++]=nums[prigt++];
            }
            else if(prigt>right)
            {
                sorted[psort++]=nums[pleft++];
            }
            else
            {
                if(nums[pleft]>nums[prigt]) sorted[psort++]=nums[prigt++];
                else sorted[psort++]=nums[pleft++];
            }
        }
        for (int k=0;k<sorted.size();k++) nums[left+k]=sorted[k];
        return res;
    }
    int reversePairs(vector<int>& nums) {
        if (!nums.size()) return 0;
        return reversePairsRecursive(nums,0,nums.size()-1);

    }
};

运行效果：

类似的思路Python代码：

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def reverseSort(left,right):
            if left is right:return 0
            res=0
            mid=int((left+right)/2)
            res+=reverseSort(left,mid)
            res+=reverseSort(mid+1,right)
            i=left
            j=mid+1
            while(i<=mid):
                while(j<=right and nums[i]>2*nums[j]): 
                    j+=1
                res+=(j-mid-1)
                i+=1
            sortList=[0 for _ in range(right-left+1)]
            pleft,pright,psort=left,mid+1,0
            while(pleft<=mid or pright<=right):
                if(pleft>mid):
                        sortList[psort]=nums[pright] 
                        psort+=1
                        pright+=1
                        
                elif(pright>right):
                    sortList[psort]=nums[pleft]
                    psort+=1
                    pleft+=1
                else:
                    if nums[pleft]>nums[pright]:
                        sortList[psort]=nums[pright] 
                        psort+=1
                        pright+=1
                    else:
                        sortList[psort]=nums[pleft]
                        psort+=1
                        pleft+=1  
            
            for i in range(len(sortList)):
                nums[left+i] = sortList[i]
            return res
        if(not len(nums)): return 0
       
        return reverseSort(0,len(nums)-1)

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-pairs