题目描述

找出逆序对的数量，分为三种情况，在左半边，右半边，和两边情况，对左边和右边排序完后，当左边的 某一位大于右边的某一位时，说明则左边剩下的数一定大于右边这个数，逆序对数为mid-i+1;

算法1

时间复杂度

C++ 代码

class Solution {
public:
    int merge_sort(vector<int>& nums,int l,int r)
    {
        if(l>=r) return 0;
        int mid=(l+r)>>1;
        int res=merge_sort(nums,l,mid)+merge_sort(nums,mid+1,r);
        int i=l,j=mid+1;
        vector<int> tmp(r-l+1);
        int k=0;
        while(i<=mid&&j<=r)
        {
            if(nums[i]<=nums[j]) tmp[k++]=nums[i++];
            else
            {
                res+=mid-i+1;
                tmp[k++]=nums[j++];
            }
        }
        while(i<=mid) tmp[k++]=nums[i++];
        while(j<=r) tmp[k++]=nums[j++];
        for(int i=l,j=0;i<=r;i++) nums[i]=tmp[j++];
        return res;
    }
    int inversePairs(vector<int>& nums) {
        return merge_sort(nums,0,nums.size()-1);
    }
};

算法2

C++ 代码

class Solution {
public: 
    int merge(vector<int> &nums,int l,int r)
    {
        if(l>=r) return 0; //只有一个元素
        int mid=(l+r)>>1; //二分
        int res=merge(nums,l,mid)+merge(nums,mid+1,r); //计算左右两个区间中的逆序对
        int i=l,j=mid+1; //定义两个指针
        vector<int> temp;
        while(i<=mid&&j<=r) //归并
        {
            if(nums[i]<nums[j]) temp.push_back(nums[i++]);
            else
            {
                temp.push_back(nums[j++]); //后面的元素小于前面的元素
                res+=mid-i+1;
            }
        }
        //无论是i或者是j，元素都比之前的数组要大，所以不可能存在新的逆序，把数组填好就可以了
        while(i<=mid) temp.push_back(nums[i++]); 
        while(j<=r) temp.push_back(nums[j++]);
        i=l;
        for(auto x:temp) nums[i++]=x;
        return res;
    }
    int inversePairs(vector<int>& nums) {
       return merge(nums,0,nums.size()-1);
    }
};