剑指 Offer 51. 数组中的逆序对

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

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

解题思路:

此题要求两个数字的逆序对，首先，暴力法不可能实现，因为此题难度为hard，那么我们自然要寻找其他方法

由于题目要求：前面一个数字大于后面数字，则组成逆序对

那么我们可以想到使用 归并排序 ，因为归并的过程中首先拆分，然后自然的进行1对1的大小比对，进行排序，我们只需要在过程中加入一个变量count进行累加，便可以return回结果

那么题目思路确认：归并排序改动

如何确认count的自增呢？这是一个非常重要的问题，可以看下面的解释

下面摘自 LeetCode官方题解

那么求逆序对和归并排序又有什么关系呢？关键就在于「归并」当中「并」的过程。我们通过一个实例来看看。

假设我们有两个已排序的序列等待合并，分别是 L = { 8, 12, 16, 22, 100 }``L={8,12,16,22,100} 和 R = { 9, 26, 55, 64, 91 }``R={9,26,55,64,91}

一开始我们用指针 lPtr = 0 指向 L 的首部，rPtr = 0 指向 R 的头部。记已经合并好的部分为 M。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = []
     |                          |
   lPtr                       rPtr

我们发现 lPtr 指向的元素小于 rPtr 指向的元素，于是把 lPtr 指向的元素放入答案，并把 lPtr 后移一位。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8]
        |                       |
      lPtr                     rPtr

这个时候我们把左边的 8 加入了答案，我们发现右边没有数比 8 小，所以 8 对逆序对总数的「贡献」为 0。

接着我们继续合并，把 9 加入了答案，此时 lPtr 指向 12，rPtr 指向 26。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8, 9]
        |                          |
       lPtr                       rPtr

此时 lPtr 比 rPtr 小，把 lPtr 对应的数加入答案，并考虑它对逆序对总数的贡献为 rPtr 相对R首位置的偏移 1（即右边只有一个数比 12 小，所以只有它和 12 构成逆序对），以此类推。

我们发现用这种「算贡献」的思想在合并的过程中计算逆序对的数量的时候，只在 lPtr 右移的时候计算，是基于这样的事实：当前 lPtr 指向的数字比 rPtr 小，但是比 RR 中 [0 ... rPtr - 1] 的其他数字大，[0 ... rPtr - 1] 的其他数字本应当排在 lPtr 对应数字的左边，但是它排在了右边，所以这里就贡献了 rPtr 个逆序对。

实际上，如果令 j = mid + 1, j在归并排序过程中发生变化，如果是nums[i] < nums[j] ，那么增加的逆序数对就是 j - (mid + 1)

AC代码：

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int len = nums.size();

        if (len < 2) {
            return 0; // 若不存在数对，直接 return 0
        }

        vector<int> helper(len);

        return reversePairs(nums, 0, len - 1, helper);
    }

private:
    int reversePairs(vector<int>& nums, int left, int right, vector<int>& helper) {
        if (left == right) {
            return 0; // 递归终止条件是只剩一个元素了（即不存在数对了）
        }

        int mid = left + (right - left) / 2; // 此算式等同于 (left + right) / 2，是为了避免溢出

        int leftPairs = reversePairs(nums, left, mid, helper); // 计算左半部分的逆序对
        int rightPairs = reversePairs(nums, mid + 1, right, helper); // 计算右半部分的逆序对

        if (nums[mid] <= nums[mid + 1]) {
            // 此判断用于加速，即如果左右都已排好序，而且左边的最大值 <= 右边的最小值，
            // 那么就不存在跨越左边和右边的逆序对了
            return leftPairs + rightPairs; 
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, helper); // 计算跨越左边和右边的逆序对

        return leftPairs + rightPairs + crossPairs;
    }

    int mergeAndCount(vector<int>& nums, int left, int mid, int right, vector<int>& helper) {
        // 本函数的前提条件是：左半部分和右半部分都是已经按升序排好序了的
        // 因为本函数是从左右部分都是只有一个元素的情况开始运行的（自底向上），所以是可以保证前提条件的
        for (int i = left; i <= right; ++i) {
            helper[i] = nums[i]; // 先填充 helper 辅助数组
        }

        int i = left, j = mid + 1; // i 和 j 分别是左半部分和右半部分的起点
        int count = 0; // count 用来统计逆序对数量

        for (int k = left; k <= right; ++k) {
            if (i == mid + 1) {
                // 假如 i 已经越过左边的边界，直接填充右半部分进 nums
                nums[k] = helper[j];
                ++j;
            } else if (j == right + 1) {
                // 假如 j 已经越过右边的边界，直接填充左半部分进 nums
                nums[k] = helper[i];
                ++i;
            } else if (helper[i] <= helper[j]) { // 注意健壮的归并排序这里要是 <=
                // 假如左边小于等于右边，那就不是逆序对，不用修改 count
                nums[k] = helper[i];
                ++i;
            } else {
                // 假如左边大于右边，是逆序对，count += 当前左边 [i, mid] 的所有元素
                // 因为假如左边是 [7,8]，右边是[5,6]，然后 i 指向 7，j 指向 5
                // 那么 5 和 7、8 都构成了逆序对，也就是此时有两对新的逆序对
                // 所以可以总结出规律：count += mid - i + 1
                nums[k] = helper[j];
                count += mid - i + 1;
                ++j;
            }
        }

        return count;
    }
};

代码来自：superkakayong(LeetCode)
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/zi-jie-ti-ku-jian-51-kun-nan-shu-zu-zhon-eipc/