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

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    // 归并排序，在外层构建一个足够大的数组
    const int N = 1e9 + 7;
    int mergeSort(int left, int right, vector<int>& data, vector<int>& tem) {
        if (left >= right)return 0;
        int mid = (left + right) / 2;
        int res = mergeSort(left, mid, data, tem) + mergeSort(mid + 1, right, data, tem);
        res = res % N;

        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++)
            tem[k] = data[k];

        for (int k = left; k <= right; k++) {
            if (i == mid + 1)
                data[k] = tem[j++];
            else if (j == right + 1 || tem[i] <= tem[j])
                data[k] = tem[i++];
            else {
                data[k] = tem[j++];
                res += mid -i + 1;
            }
        }
        return res % N;
    }
    int InversePairs(vector<int>& nums) {
        // write code here
        int n = nums.size();
        vector<int>tem(n-1);
        return mergeSort(0, n - 1, nums, tem);
    }
};