LCR 170

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

难度：困难

高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/

求数组中的逆序对只需要在归并排序的代码的基础上添加一行代码即可。当 nums[i] > nums[j] 时，说明从 i 到 mid 这 (mid - i + 1) 个元素都与 j 构成了逆序对，更新全局变量 cnt。

if (nums[i] <= nums[j]) {
    tmp[k] = nums[i];
    i++;
} else {
    cnt += (mid - i + 1);
    tmp[k] = nums[j];
    j++;
}

时间复杂度：O(nlogn)。由于归并排序每次都将当前待排序的序列折半成两个子序列递归调用，然后再合并两个有序的子序列，而每次合并两个有序的子序列需要 O(n) 的时间复杂度，根据主定理我们可以得出归并排序的时间复杂度为 O(nlogn)。

空间复杂度：O(n)。我们需要额外 O(n) 空间的 tmp 数组，且归并排序递归调用的层数最深为 logn，所以我们还需要额外的 O(logn) 的栈空间，所需的空间复杂度即为 O(n+logn) = O(n)。

class Solution {
    vector<int> tmp;
    int cnt = 0;
public:
    void merge_sort(vector<int>& nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i == mid + 1) {
                tmp[k] = nums[j];
                j++;
            } else if (j == r + 1) {
                tmp[k] = nums[i];
                i++;
            } else if (nums[i] <= nums[j]) {
                tmp[k] = nums[i];
                i++;
            } else {
                cnt += (mid - i + 1);
                tmp[k] = nums[j];
                j++;
            }
        }
        for (int k = l; k <= r; k++) {
            nums[k] = tmp[k];
        }
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        tmp.resize(n);
        merge_sort(nums, 0, n - 1);
        return cnt;
    }
};