分治思想实战：归并排序与数组逆序对详解

流程解析

48. 数组中的逆序对

题目链接

• LCR 170. 交易逆序对的总数 - LeetCode

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

题目示例

解法：利用归并排序的过程——分治

算法思路

统计逆序对最经典的方法就是基于归并排序。我们不需要枚举所有数对，而是利用归并过程中「两个子数组均有序」的特性来快速计算。

为什么可以用归并排序？ 将数组从中间划分为左右两部分，逆序对只可能产生于三种情况：

1. 两个元素都在左半部分；
2. 两个元素都在右半部分；
3. 一个在左半部分，一个在右半部分。

前两种情况可以通过递归解决，第三种情况（跨区间逆序对）正是归并排序合并阶段需要处理的。当我们在合并两个有序数组时，如果发现右侧当前元素小于左侧当前元素，那么左侧剩余的所有元素都大于该右侧元素，它们都能与该右侧元素构成逆序对。

如何高效统计？ 在合并过程中维护一个计数器。假设当前正在比较 nums[cur1] 和 nums[cur2]：

• 若 nums[cur1] <= nums[cur2]：左侧元素较小，不构成逆序，放入临时数组。
• 若 nums[cur1] > nums[cur2]：发现逆序。由于左侧数组已排序，[cur1, mid] 范围内的所有元素都大于 nums[cur2]。因此，逆序对数量增加 mid - cur1 + 1。

C++ 代码实现

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 {
                // 关键逻辑：左侧剩余元素均大于右侧当前元素
                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];
        }
    }
};

流程解析

通过上述分析，我们可以看出归并排序不仅是一个排序工具，其合并过程的单调性特性使其成为解决逆序对问题的利器。时间复杂度稳定在 O(nlogn)，空间复杂度为 O(n)。