题解 | #数组中的逆序对#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int count = 0; 
    const int MOD = 1000000007;


    void merge(vector<int> &v,int left,int mid,int right){
        
        vector<int> temp ;
        
        int l = left;
        int r = mid+1;
        
        while(l<= mid and r<=right){
            if(v[l]<v[r]){
                temp.push_back(v[l]);
                l++;
            }
        //交换的地方		
            if(v[l]>v[r]){
                count+= mid - l+1;
                count = count % MOD;
                temp.push_back(v[r]);
                r ++;
            }
        }
        while(l<=mid){
            temp.push_back(v[l]);
            l++;
        }
        while(r<=right){
            temp.push_back(v[r]);
            r++;
        }
        
        for (int i=left;i<=right;i++){
            v[i]= temp[i-left];
        }
        
    }


    void mergeSort(vector<int> &v,int left,int right){
        if(left>=right) return;
        int mid  = left  + (right - left)/2;

    //	cout<<mid; 
        mergeSort(v,left,mid);
        mergeSort(v,mid+1,right);
        merge(v,left,mid,right);
        
        
    }

    int InversePairs(vector<int>& nums) {
        // write code here
        mergeSort(nums,0,nums.size()-1);
        return count;
    }
};

⚠️：

1.使用归并排序

mergeSort 是一种分治法的排序算法，时间复杂度为 𝑂(𝑛log𝑛)

mergeSort 将数组不断二分，直到每个子数组只有一个元素。这需要 log𝑛步。

每一步 mergeSort 调用 merge 来合并两个有序子数组。合并操作需要线性时间

𝑂(𝑛)

2.count+= mid - l+1; 最重要‼️

eg：

3，6，7 1 5

这里5 能 6，5 7，5

此时l指向 6 r指向5

然后right部分 一定是升序 不可能比5小，所以只能和左边组队，而左边也不是全部 是l和mid之间的部分可以组队