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

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int mod = 1000000007;
    int merge(int l, int r, vector<int>& data, vector<int>& temp) {
        if (l >= r) {
            return 0;
        }
        int mid = (l + r) / 2;
        int res = merge(l, mid, data, temp) + merge(mid + 1, r, data, temp);
        res %= mod;
        temp.resize(r - l + 1);
        int i = l, j = mid + 1, k = l;
        while (i <= mid && j <= r) {
            if (data[i] < data[j]) {
                temp[k++] = data[i++];
            }
            else {
                temp[k++] = data[j++];
                res += mid - i + 1;
            }
        }
        while (i <= mid) {
            temp[k++] = data[i++];
        }
        while (j <= r) {
            temp[k++] = data[j++];
        }
        for (i = l; i <= r; i++) {
            data[i] = temp[i];
        }
        return res % mod;
    }
    
    int InversePairs(vector<int>& nums) {
        // write code here
        vector<int> temp;
        temp.resize(nums.size() - 1);
        return merge(0, nums.size() - 1, nums, temp);         
    }
};