一、题目

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

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

示例：
输入: [2,4,3,5,1]
输出: 3

二、代码

class Solution {
public:
    int mergeSort(vector<int> &nums,int left,int right){
        int len=right-left+1;
        if(len==0||len==1) return 0;

        int mid=(left+right)/2;
        int Ans=mergeSort(nums,left,mid)+mergeSort(nums,mid+1,right);

        //get merged important reverse pairs 
        int i=left,j=mid+1;
        while(i<=mid&&j<=right){
            if((long long)nums[i]>2LL*nums[j]){
                Ans+=mid-i+1; j++;
            }else i++;   
        } 

        //merge
        i=left,j=mid+1;
        int k=0;
        vector<int> tmp(len);
        while(i<=mid||j<=right){
            if(i>mid){
                tmp[k++]=nums[j++];
            }else if(j>right){
                tmp[k++]=nums[i++];
            }else tmp[k++]=nums[i]<=nums[j]?nums[i++]:nums[j++];
        }
        for(int i=left;i<=right;++i){
            nums[i]=tmp[i-left];
        }
        return Ans;
    }

    int reversePairs(vector<int>& nums) {
        return mergeSort(nums,0,nums.size()-1);
    }
};

解题思路：

1. 显然，这道题是可以用二分法的递归的，那么想到了归并排序
2. 对于已经排好序的左右序列，i，j表示左右序列的下标，当nums[i]>2*nums[j]时，由于左序列中i右边的值都比nums[i]大，所以他们也是符合条件的，ans直接加上mid-i+1即可，并右移j。否则右移i。

要点：

1. 首先要计算答案，然后将两个序列归并排序
2. vector最好初始化时分配空间，然后直接用[]下标赋值，不要用push_back（性能太慢）

最后

以上就是彪壮星星为你收集整理的leetcode 493. 翻转对一、题目二、代码的全部内容，希望文章能够帮你解决leetcode 493. 翻转对一、题目二、代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。