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

#include <vector>
class Solution {
public:
    int mod = 1000000007;
    int InversePairs(vector<int>& nums) {
        //
        int n = nums.size();
        vector<int> temp(n); 
        int ret = 0;
        merge_sort(nums, 0, n - 1, temp, ret); //这里记住temp一定得是引用类型的，不然超出内存
        return ret;

    }
   void  merge_sort(vector<int>& nums, int left, int right, vector<int>& temp, int & ret){
        if(left >= right) return;//当只有一个元素的时候进行返回

        int mid = left + ((right - left)>>1);
        merge_sort(nums, left, mid, temp, ret);
        merge_sort(nums, mid + 1, right, temp, ret);
        merge_(nums, left, mid, right, temp, ret); //此时进行合并，两个集合之间进行计算有多少逆序数

   }
   void merge_(vector<int> & nums, int left, int mid, int right, vector<int> &temp, int & ret){
        int i = left, j = mid + 1, k = 0;
        while(i <= mid && j <= right){ 
            if(nums[i] >nums[j]){
                temp[k++] = nums[j++];
                ret += (mid - i + 1); //只有当i指向的元素大于j指向的元素才计算逆序对，同时将temp中的元素进行更新，temp存储的是有序的
                ret %= mod;
            }
            else{
                temp[k++] = nums[i++];
            }
        }
        //下面两个while用来处理i或j已经到达终点的情况，而另外一个（i或j） 还没有完全更新至temp中
        while(i <= mid) temp[k++] = nums[i++];
        while(j <= right) temp[k++] = nums[j++];
        for(k = 0, i = left; i <= right; ++i, ++k){
            nums[i] = temp[k]; //更新left到right下标中的元素，局部有序
        }
   }
};