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

class Solution {
  public:
    const int MOD = 1000000007;

// 归并排序中的合并函数，同时计算逆序对数量
    int merge(vector<int>& nums, int left, int mid, int right, vector<int>& temp) {
        int i = left;    // 左子数组的起始位置
        int j = mid + 1; // 右子数组的起始位置
        int k = 0;       // 临时数组的索引
        int inv_count = 0; // 逆序对数量

        // 合并两个有序数组，并计算逆序对
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                inv_count += (mid - i +
                              1); // nums[i]到nums[mid]都比nums[j]大，形成逆序对
            }
        }

        // 将剩余元素添加到临时数组
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        // 将排序后的数组复制回原数组
        for (i = 0; i < k; i++) {
            nums[left + i] = temp[i];
        }

        return inv_count % MOD; // 防止溢出
    }

// 归并排序函数，同时计算逆序对
    int mergeSort(vector<int>& nums, int left, int right, vector<int>& temp) {
        int inv_count = 0;
        if (left < right) {
            int mid = left + (right - left) / 2;
            inv_count += mergeSort(nums, left, mid, temp);  // 排序左半部分
            inv_count += mergeSort(nums, mid + 1, right, temp); // 排序右半部分
            inv_count += merge(nums, left, mid, right, temp); // 合并并计算逆序对
        }
        return inv_count % MOD;
    }

    int InversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> temp(n); // 临时数组，用于归并排序
        return mergeSort(nums, 0, n - 1, temp) % MOD;  // 防止溢出
    }
};