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

#include <algorithm>
#include <vector>
#define MOD 1000000007
class Solution {
public:
    int InversePairs(vector<int> data) {
        vector<int> tmp;
        for(int i = 0;i < data.size();i++)
            tmp.push_back(data[i]);
        return sort(data, 0, data.size(), tmp);
    }
private:
    int Merge(vector<int> &data, int left, int mid, int right,vector<int> &tmp){
        int p = 0;
        int i = left;
        int j = mid;
        int inverse_cnt = 0; 
        while(i<mid&&j<right){
            if(data[i]<=data[j])
                tmp[p++] = data[i++];
            else{
                inverse_cnt += mid - i;
                tmp[p++] = data[j++];
            }
        }
        while(i<mid)
            tmp[p++] = data[i++];
        while (j<right) 
            tmp[p++] = data[j++];
        p = 0;
        for(i = left;i<right;i++)
            data[i] = tmp[p++];
        return inverse_cnt;
    }
    int sort(vector<int> &data, int left, int right,vector<int> &tmp){
        if(right-left==1){
            return 0;
        }
        int mid = (left+right)/2;
        int inverse1 = 0;
        int inverse2 = 0;
        inverse1 = sort(data, left, mid, tmp) % MOD;
        inverse2 = sort(data, mid, right, tmp) % MOD;
        return (inverse1+inverse2+Merge(data, left, mid, right,tmp)%MOD) % MOD;
    }
};

这个题就是用归并排序的方法，核心思想就是数组一分为二，先求左边的逆序数，再求右边的逆序数，再求左右之间产生的逆序数。将三者相加就是该数组的逆序数。依次递归，当数组只有一个数字时，逆序数为0。用归并排序是为了求左右两边之间产生的逆序数。思路如下：假设a，b为有序数组，则将a，b merge的时候，如果出现b当前元素（索引为j）比a当前元素（索引为i）小的情况，就说明a当前元素及后面的所有元素都比b当前的元素大，也就是当前的b元素产生的逆序数为a.size() - i. 由此可求出a和b合并时产生的逆序数