归并排序与数组逆序对详解

流程解析

48. 数组中的逆序对

题目描述

计算数组中所有逆序对的总数。逆序对定义为：i < j 且 nums[i] > nums[j]。

解法思路

利用归并排序的合并过程统计逆序对数量。当合并两个有序子数组时，如果左边的元素大于右边的元素，说明左边剩余的所有元素都与当前右边元素构成逆序对。

具体分类如下：

1. 逆序对全部来自左半部分（递归求解）。
2. 逆序对全部来自右半部分（递归求解）。
3. 逆序对跨越左右两部分（在合并时统计）。

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 k = left; k <= right; k++) {
            nums[k] = tmp[k - left];
        }
    }
};

流程解析