分治-归并排序-逆序对问题

猫咪-9527

发布于 2025-04-06 21:13:19

10900

代码可运行

文章被收录于专栏：猫咪-9527猫咪-9527

运行总次数：0

代码可运行

1.升序（以右边的合并组为基准）

找出左边有多少个数比我(nums[right])大

应该在每一次合并之前，进行逆序对查找
每一个该合并的组都是按升序排列，所以当nums[left]<nums[right]时，应该left++，因为都是升序，所以当nums[left]>nums[right]，right++时，left从当前位置不动。

class Solution {
public:
    vector<int> ret;
    int vim=0;
    int reversePairs(vector<int>& record) {
        ret.resize(record.size());
        mergesort(record,0,record.size()-1);
        return vim;
    }
    void merge(vector<int>&nums,int low,int high,int mid)
    {
        int left=low,right=mid+1, i=0;
        while(left<=mid&&right<=high)
        {
             if(nums[left]<=nums[right]) ret[i++]=nums[left++];
            else  
            {
                ret[i++]=nums[right++];
                vim+=(mid+1-left);
            }
        }
        while(left<=mid) ret[i++]=nums[left++];
        while(right<=high) ret[i++]=nums[right++];
        for(int i=0;i<high-low+1;i++)
        {
            nums[i+low]=ret[i];
        }
    }
    void mergesort(vector<int>&nums,int low,int high)
    {
        if(low>=high) return;
        int mid=(low+high)/2;
        mergesort(nums,low,mid);
        mergesort(nums,mid+1,high);
        merge(nums,low,high,mid);
        
    }
};

2.降序（以左边的合并组为基准）

找出多少个数比我小

合并过程：

class Solution {
public:
    vector<int> ret;
    int vim=0;
    int reversePairs(vector<int>& record) {
        ret.resize(record.size());
        mergesort(record,0,record.size()-1);
        return vim;
    }
    void merge(vector<int>&nums,int low,int high,int mid)
    {
        int left=low,right=mid+1, i=0;
        while(left<=mid&&right<=high)
        {
             if(nums[left]>nums[right]) 
             {
                vim+=(high-right+1);
                ret[i++]=nums[left++];
             }
            else  
            {
                ret[i++]=nums[right++];
            }
        }
        while(left<=mid) ret[i++]=nums[left++];
        while(right<=high) ret[i++]=nums[right++];
        for(int i=0;i<high-low+1;i++)
        {
            nums[i+low]=ret[i];
        }
    }
    void mergesort(vector<int>&nums,int low,int high)
    {
        if(low>=high) return;
        int mid=(low+high)/2;
        mergesort(nums,low,mid);
        mergesort(nums,mid+1,high);
        merge(nums,low,high,mid);
        
    }
};

对比：

降序升序 void merge(vector<int>&nums,int low,int high,int mid) { int left=low,right=mid+1, i=0; while(left<=mid&&right<=high) { if(nums[left]>nums[right]) { vim+=(high-right+1); ret[i++]=nums[left++]; } else ret[i++]=nums[right++]; } while(left<=mid) ret[i++]=nums[left++]; while(right<=high) ret[i++]=nums[right++]; for(int i=0;i<high-low+1;i++) { nums[i+low]=ret[i]; } } void merge(vector<int>&nums,int low,int high,int mid) { int left=low,right=mid+1, i=0; while(left<=mid&&right<=high) { if(nums[left]<=nums[right]) ret[i++]=nums[left++]; else { ret[i++]=nums[right++]; vim+=(mid+1-left); } } while(left<=mid) ret[i++]=nums[left++]; while(right<=high) ret[i++]=nums[right++]; for(int i=0;i<high-low+1;i++) { nums[i+low]=ret[i]; } }