算法实战：归并排序与数组逆序对详解

48. 数组中的逆序对

核心思路

利用归并排序求逆序数是经典解法。主要是在归并排序的合并过程中统计出逆序对的数量。我们将问题分解为三个部分：

1. 左半部分的逆序对。
2. 右半部分的逆序对。
3. 跨越左右两部分的逆序对（一个在左，一个在右）。

前两部分通过递归解决，第三部分在合并时处理。当合并两个有序数组时，如果左边的当前元素大于右边的当前元素，说明左边剩余的所有元素都大于右边当前元素，它们都能与右边当前元素构成逆序对。

代码实现

class Solution {
public:
    int count = 0;
    vector<int> tmp;

    int reversePairs(vector<int>& record) {
        tmp.resize(record.size());
        mergesort(record, 0, record.size() - 1);
        return count;
    }

    void mergesort(vector<int>& nums, int left, int right) {
        if (left >= right) return;

        int mid = (right - left) / 2 + left;
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        
        // 合并过程同时统计逆序对
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                // 关键逻辑：nums[cur1] > nums[cur2]
                // 此时 [cur1, mid] 区间的所有元素都大于 nums[cur2]
                count += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];

        for (int i = left; i <= right; i++) {
            nums[i] = tmp[i - left];
        }
    }
};