题解 | 数组中的逆序对

#include <vector>
using namespace std;

class Solution {
public:
    int mod = 1000000007;

    int mergeSort(vector<int>& data, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int count = (mergeSort(data, left, mid) + mergeSort(data, mid + 1, right)) % mod;
        count = (count + merge(data, left, mid, right)) % mod;
        return count;
    }

    int merge(vector<int>& data, int left, int mid, int right) {
        vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        int count = 0;
        while (i <= mid && j <= right) {
            if (data[i] <= data[j]) {
                temp[k++] = data[i++];
            } else {
                temp[k++] = data[j++];
                count = (count + mid - i + 1) % mod;
            }
        }
        while (i <= mid) {
            temp[k++] = data[i++];
        }
        while (j <= right) {
            temp[k++] = data[j++];
        }
        for (int i = left, k = 0; i <= right; i++, k++) {
            data[i] = temp[k];
        }
        return count;
    }

    int InversePairs(vector<int> data) {
        if (data.empty()) return 0;
        return mergeSort(data, 0, data.size() - 1);
    }
};

mergeSort 函数：主要负责递归分解数组

merge 函数：负责合并已排序的子数组，并统计所有的逆序对

将排序结果复制回原数组是因为归并排序是递归算法，每一层的合并操作都依赖于下层已经排序好的子数组。如果不将结果复制回原数组，上层的合并操作将无法正确进行。