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

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    const int p = 1000000007;
    int InversePairs(vector<int>& nums) {
        // write code here
        int res = 0;
        int n = nums.size();
        vector<int> temp(n);
        sort(nums, 0, n - 1, temp, res);
        return res % p;
    }
    void sort(vector<int>& nums, int left, int right, vector<int>& temp, int& res) {
        if (left >= right)
            return;
        int mid = (left + right) / 2;
        sort(nums, left, mid, temp, res);
        sort(nums, mid + 1, right, temp, res);
        for (int k = left; k <= right; k++) {	//temp记录待合并数组的信息
            temp[k] = nums[k];
        }
        int i = left, j = mid + 1;	//i，j分别表示待合并两数组的当前待插入索引
        for (int k = left; k <= right; k++) {
            if (i > mid) {	//第一个待合并数组空了
                nums[k] = temp[j++];
            } else if (j > right) {	//第二个待合并数组空了
                nums[k] = temp[i++];
            } else if (temp[i] < temp[j]) {	//第一个待合并数组当前值 小于 第二个待合并数组当前值
                nums[k] = temp[i++];
            } else if (temp[i] > temp[j]) {	//第一个待合并数组当前值 大于 第二个待合并数组当前值
                res += mid - i + 1;
                res %= p;
                nums[k] = temp[j++];
            }
        }
    }
};