归并排序相关问题

归并排序模板：

void merge(vector<int>& nums, int l, int r){
        if ( l >= r) return 0;//只有一个数
        int mid = l+r >>1;
        //递归左右排序
        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++]);
        }
        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;
    }

1、求数组逆序对：

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

在归并排序中，返回int用来计算逆序对；

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;//后面的数组大于前面的个数
            }
        }
        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;
        /*for(int i = l ; i <= r; i++) cout << nums[i] << ' ';
        cout << endl;*/
        return res;
    }
    int inversePairs(vector<int>& nums) {
        return merge(nums,0,nums.size()-1);
    }
};