BM20 数组中的逆序对

剑指 Offer 51. 数组中的逆序对

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

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

C++

class Solution {
public:
    int cnt = 0;

    void merge_cnt(vector<int>& data, int l, int r){
        if(l >= r) return;
        int mid = l + r >> 1;
        merge_cnt(data, l, mid); 
        merge_cnt(data, mid + 1, r);

        int i = l, j = mid + 1;
        vector<int> t;
        while(i <= mid && j <= r){
            if(data[i] <= data[j]) t.push_back(data[i ++]);
            else {
                t.push_back(data[j ++]);
                // 逆序对的个数为    左子数组的终点- 当前左子数组的当前指针
                cnt += mid + 1 - i;
                cnt %= 1000000007;
            }
        }
        while(i <= mid) t.push_back(data[i ++]);
        while(j <= r) t.push_back(data[j ++]);
        for(int i = l, j = 0; j < t.size(); i ++, j ++) data[i] = t[j];
    }

    int InversePairs(vector<int> data) {
        merge_cnt(data, 0, data.size() - 1);
        return cnt;
    }
    
};