题目描述

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

示例 1:
输入: [7,5,6,4]
输出: 5

主要是对归并排序重新走了一遍 值得注意的是
在累加逆序对个数的过程中要注意的是

当nums[l1]>nums[l2]:
cnt += (mid-l1+1);//l1>l2，l1之前所有的元素都l2,
l2++;//注意这里移动了l2，因此对l1做累加 ，不然会重复累加
如 3，2，1；l1 = 0,l2 = 1,如果累加l2的话，在l2=1,2时做了重复的累加

#include<vector>
#include<iostream>
using namespace std;


class Solution {
    vector<int> auxiliary;
public:
    int reverse_cnt(vector<int>&nums,int start,int mid,int end){
        //左侧区间是[start,mid-1].
        //右侧区间是[mid,end]
        //原地归并不太会，新开一个数组
        int l_1 = start;
        int l_2 = mid+1;
        int cnt = 0;
        int i = start;
        while(l_1<=mid&&l_2<=end){
            if(nums[l_1]>nums[l_2]){
                cnt+=(mid-l_1+1);//l1>l2 后续的所有l1都会大于l2
                auxiliary[i] = nums[l_2++];
            }else{
                auxiliary[i] = nums[l_1++];
            }
            i++;
        }
        if(i>end){
            cout<<"error"<<endl;
            return 0;
        }
        if(l_1<=mid)copy(nums.begin()+l_1,nums.begin()+mid+1,auxiliary.begin()+i);
        if(l_2<=mid)copy(nums.begin()+l_2,nums.begin()+end+1,auxiliary.begin()+i);
        copy(auxiliary.begin()+start,auxiliary.begin()+end+1,nums.begin()+start);
        return cnt;
    }

    int merge_sort(vector<int>& nums,int start,int end) {
        if(start>=end)return 0;
        int mid = start+(end-start)/2;
        int val_l = merge_sort(nums,start,mid);
        int val_r = merge_sort(nums,mid+1,end);
        //假定前半部分有序，后半部分也有序，计算合并过程产生的冲突
        return val_l+val_r+reverse_cnt(nums,start,mid,end);
    }

    int reversePairs(vector<int>& nums) {
        //归并排序求逆序对个数
        auxiliary = vector<int>(nums);
        return merge_sort(nums,0,nums.size()-1);
    }
};