题解 | 数组中的逆序对

#include <limits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */

    int merge(vector<int>& nums, int left, int mid, int right)
    {
        int ans = 0;
        vector<int> leftArray(nums.begin() + left, nums.begin() + mid + 1);
        vector<int> rightArray(nums.begin() + mid + 1, nums.begin() + right + 1);
        int leftLeft = leftArray.size();
        leftArray.insert(leftArray.end(), numeric_limits<int>::max());
        rightArray.insert(rightArray.end(), numeric_limits<int>::max());
        int leftIdx = 0, rightIdx = 0;
        for (int i = left; i <= right; i++)
        {
            if (leftArray[leftIdx] > rightArray[rightIdx])
            {
                nums[i] = rightArray[rightIdx];
                rightIdx ++;
                ans += leftLeft;
            }
            else {
                nums[i] = leftArray[leftIdx];
                leftIdx ++;
                leftLeft --;
            }
        }
        return ans % 1000000007;
    }

    
    int sort(vector<int>& nums, int left, int right)
    {
        if (left >= right)
            return 0;
        int mid = (left + right) >> 1;
        int ans1 = sort(nums, left, mid);
        int ans2 = sort(nums, mid + 1, right);
        return (merge(nums, left, mid, right) + ans1 + ans2) % 1000000007;
    }

    int InversePairs(vector<int>& nums) {
        // write code here
        int end = nums.size() - 1;
        return sort(nums, 0, end);
    }
};