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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        // write code here
        merge_sort(nums, 0, nums.size() - 1);
        return res;
    }
private:
    int res = 0;
    void merge_sort(vector<int>& nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        merge_sort(nums, start, mid);
        merge_sort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    void merge(vector<int>& nums, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        vector<int> tmp(end - start + 1, 0);
        int k = 0;
        while (i <= mid && j <= end) {
            if (nums[i] > nums[j]) {
                res += (mid - i) + 1;
                res %= 1000000007;
                tmp[k++] = nums[j++];
            } else {
                tmp[k++] = nums[i++];
            }
        }
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= end) {
            tmp[k++] = nums[j++];
        }
        for (int l = start, k = 0; l <= end; l++, k++) {
            nums[l] = tmp[k];
        }
    }
};