题解 | #数组中的逆序对# 官方代码+Chat的注释

#include <bits/types/struct_tm.h>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int mod = 1000000007;
    int mergeSort(int left, int right, vector<int>& data, vector<int>& tmp) {
        // 考虑到归并排序的特点，其本身具有递归的特点，也具有阶段性排序的特点。
        // 递归属性(类似后序遍历的顺序)
        // 1、递归结束判断
        // 注意这里一定要是大于等于，因为元素个数是1的情况下就一定是有序的，对于左闭右闭的区间来说相等即为停止条件。
        if (left >= right) return 0;
        // 2、递归延续逻辑
        int mid = (left + right) / 2;
        int res = mergeSort(left, mid, data, tmp) + mergeSort(mid + 1, right, data,tmp);
        res %= mod;
        // 3、本层逻辑处理
        // 确定左右区间的起点
        int i = left, j = mid + 1;
        // 使用 temp 数组暂存当前分段的数据。
        for (int k = left; k <= right; k++) {
            tmp[k] = data[k];
        }
        // 归并与计数
        for (int k = left; k <= right; k++) {
            // 这里检查左子数组是否已经完全复制回主数组 data
            if (i == mid + 1) {
                data[k] = tmp[j++];
            }
            // 这一行检查两种情况：一是右子数组是否已经完全复制回 data（即 j 超过了 right），二是左子数组的当前元素是否小于或等于右子数组的当前元素。
            else if (j == right + 1 || tmp[i] <= tmp[j]) {
                data[k] = tmp[i++];
            }
            // 这是处理逆序对的关键代码。如果以上条件都不满足，即 temp[i] 大于 temp[j]，表明存在逆序对。
            else {
                data[k] = tmp[j++];
                res += mid - i + 1;
            }
        }

        return res % mod;
    }

    int InversePairs(vector<int>& nums) {
        // write code here
        int n = nums.size();
        // r每次都是先赋值再判断，所以初始值对程序运行没有影响
        vector<int> r(n);
        return mergeSort(0, n - 1, nums, r);
    }
};