归并排序原理及数组逆序对求解

算法流程解析

48. 数组中的逆序对

题目链接

• LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

题目描述

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请计算总共有多少个逆序对。

题目示例

输入：[7,5,6,4] 输出：5 解释：逆序对为 (7,5), (7,6), (7,4), (5,4), (6,4)。

解题思路

利用归并排序的合并过程统计逆序对数量，时间复杂度可优化至 O(nlogn)。

为什么能用归并排序？ 逆序对分为三类：

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

前两类可以通过递归解决，第三类可以在合并两个有序子数组时快速统计。

如何统计？ 在合并过程中，若左指针指向的元素 nums[cur1] 大于右指针指向的元素 nums[cur2]，说明 nums[cur1] 及其右侧所有剩余元素都大于 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)。在合并过程中统计逆序对数量，避免了暴力枚举带来的高开销。