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

归并排序
时间复杂度：
空间复杂度：

class Solution {
public:
    const int MOD = 1e9 + 7;
    int ans = 0;
    void merge(vector<int>& data, int left, int mid, int right){
        vector<int> vec(right - left + 1);
        int idx = 0;
        int i = left, j = mid + 1;
        while(i <= mid && j <= right){
            if(data[i] <= data[j]) vec[idx ++] = data[i ++];
            else{
                ans += mid - i + 1; //统计逆序对
                ans %= MOD;
                vec[idx ++] = data[j ++];
            }
        }
        while(i <= mid) vec[idx ++] = data[i ++];
        while(j <= right) vec[idx ++] = data[j ++];
        for(int i = 0; i < right - left + 1; i ++){
            data[left + i] = vec[i];
        }
    }
    void mergeSort(vector<int>& data, int left, int right){
        if(left < right){
            int mid = left + (right - left) / 2;
            mergeSort(data, left, mid);
            mergeSort(data, mid + 1, right);
            merge(data, left, mid, right);
        }
    }
    int InversePairs(vector<int> data) {
        mergeSort(data, 0, data.size() - 1);
        return ans;
    }
};