归并排序实战：计算右侧小于当前元素个数与翻转对

归并排序实战：计算右侧小于当前元素个数与翻转对

在算法面试中，涉及数组统计的问题往往需要高效的解决方案。今天我们来深入探讨两个经典的 LeetCode 题目，它们都可以通过**归并排序（Merge Sort）**的分治思想来解决。

49. 计算右侧小于当前元素的个数

题目描述

给定一个整数数组 nums，按要求返回一个新数组 counts。其中 counts[i] 表示在 nums[i] 右边且比它小的元素个数。

例如输入 [5, 2, 6, 1]，输出应为 [2, 1, 1, 0]。

核心思路

这道题和求逆序对非常相似，但区别在于我们需要知道每个位置对应的具体数量，而不是总数。

归并排序在合并两个有序子数组时，如果左边的元素大于右边的元素，说明左边这个元素后面有若干个比它小的数。但在排序过程中，元素的原始下标会发生变化，因此我们需要维护一个辅助数组来记录每个元素原本的索引。

实现代码

class Solution {
public:
    vector<int> counts;
    vector<int> index; // 记录 nums 中当前元素的原始下标
    vector<int> tmp;
    vector<int> tmpi; // 临时记录合并后对应元素位置变化下标随之变化的数组

    vector<int> countSmaller(vector<int>& nums) {
        counts.resize(nums.size());
        index.resize(nums.size());
        tmp.resize(nums.size());
        tmpi.resize(nums.size());
        
        // 初始化 index，使得 nums 每个元素下标和 index 一一对应
        for(int i = 0; i < nums.size(); i++) {
            index[i] = i;
        }
        mergesort(nums, 0, nums.size() - 1);
        return counts;
    }

    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]) {
                // 重点：因为 index[cur1] 始终是 cur1 当前元素的原始下标
                // 所以不管当前元素位置怎么变化，counts[index[cur1]] 的位置都不会变
                counts[index[cur1]] += right - cur2 + 1;
                tmpi[i] = index[cur1];
                tmp[i++] = nums[cur1++];
            } else {
                tmpi[i] = index[cur2];
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid) {
            tmpi[i] = index[cur1];
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= right) {
            tmpi[i] = index[cur2];
            tmp[i++] = nums[cur2++];
        }
        for(int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
            index[j] = tmpi[j - left];
        }
    }
};

流程解析

在合并阶段，当 nums[cur1] > nums[cur2] 时，意味着 nums[cur1] 及其左侧剩余的所有元素都比 nums[cur2] 大。由于右半部分已经有序，从 cur2 到 right 的所有元素都小于 nums[cur1]，数量为 right - cur2 + 1。通过 index 数组，我们可以准确地将这个计数累加到原数组对应位置的 counts 中。

---

50. 翻转对

题目描述

给定一个数组 nums，如果 i < j 且 nums[i] > 2 * nums[j]，则称 (i, j) 为一个翻转对。返回数组中翻转对的总数。

核心思路

翻转对和逆序对的定义大同小异，只是条件变成了 nums[i] > 2 * nums[j]。我们依然可以使用归并排序的思想，将问题分解为三部分：左半区间翻转对的数量、右半区间翻转对的数量、一左一右选择时翻转对的数量。

关键区别在于：上一道题可以在合并的同时计算，但这道题要求的是左边元素大于右边元素的两倍。如果在合并过程中直接操作，可能会破坏顺序导致无法快速判断。因此，我们需要先统计满足条件的翻转对数量，再进行归并排序。

实现代码

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

    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        mergesort(nums, 0, nums.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;
        while(cur1 <= mid && cur2 <= right) {
            // 当左边大于右边的两倍才会进行求值
            if((long long)nums[cur1] > 2LL * nums[cur2]) {
                count += right - cur2 + 1;
                cur1++;
            } else {
                cur2++;
            }
        }
        
        // 再执行标准的归并排序合并
        cur1 = left;
        cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] > nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                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];
        }
    }
};

流程解析

这里需要注意类型转换，使用 long long 防止乘法溢出。统计阶段利用了两个子数组分别有序的特性：对于左边的每一个 cur1，找到第一个满足 nums[cur1] <= 2 * nums[cur2] 的 cur2，那么 cur2 之后的所有元素都满足翻转对条件。统计完成后，再像普通归并排序一样合并数组，保证上一层递归能继续处理。

---

总结

这两道题展示了归并排序在统计类问题中的强大能力。49 题通过维护原始索引解决了动态位置下的计数问题；50 题则通过分离'统计'与'合并'步骤，巧妙处理了非单调的比较条件。掌握这种分治策略，面对类似的逆序对变种问题时就能游刃有余。