题解 | 数组中的逆序对 wok写出来了 看注释 再看看题解

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        // write code here
        //用归并写
        int p=0;
        int size=nums.size();
        vector<int> assist(size);
        mergesort(nums, 0, size-1, p,assist);
        return p;


    }
    void mergesort(vector<int>& nums,int left,int right,int& p,vector<int>& assist){
       //这里传p只是传值 要传引用
        if(left>=right)return;
        int mid=(left+right)/2;
        mergesort(nums,left, mid,p,assist);
        mergesort(nums,mid+1, right,p,assist);
        merge(nums,left,right,mid,p,assist);

    }
    void merge(vector<int>& nums,int left,int right,int mid,int& p,vector<int>& assist){
        /*
        反正都要存在一个数组的复制情况，排列之后把它再复制到原数组，就不用像这样复制原来的数组了
        vector<int> assist;
        assist.assign(nums.begin()+left, nums.begin()+right);
        */
        
        int low=left,high=mid+1;
        int cur=left;
        while(low<=mid&&high<=right){
            if(nums[high]<nums[low]){
                p=(p+mid-low+1)%1000000007;
                //这里p不只是加1，当右边的元素较小 被加入新数组时，它实际比左侧的该指针往后的所有数都小 原顺序排在它们后面 所以逆序数应该是mid-low+1；
                assist[cur]=nums[high];
                high++;
                cur++;
            }
            else{
                assist[cur]=nums[low];
                low++;
                cur++;
            }
        }

        //可以优化 
        //逻辑错误 当只剩左边时 尽管这些确实比右边的大，但这个逆序关系在前面已经被记录了。只剩右边时 没有逆序关系。
            while(high<=right){
                assist[cur]=nums[high];
                cur++;
                high++;
                //p=(p+1)%1000000007;
            }
            while(low<=mid){
                assist[cur]=nums[low];
                cur++;
                low++;
                //p=(p+1)%1000000007;
            }
        while(left<=right){//思考这里是等号
            nums[left]=assist[left];
            left++;
        }
       // vector<int>().swap(assist);


    }
};