剑指offer 53. 数组中的逆序对

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

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

输入一个数组，求出这个数组中的逆序对的总数。

数据范围

给定数组的长度 [0,100]。

样例

输入：[1,2,3,4,5,6,0]

输出：6

方法一：归并排序 O(nlogn)

我们可以在进行归并排序的过程中，计算逆序对的个数。

归并排序每趟排序都是对已知的两个有序的序列进行排序，我们可以在排序过程中，利用该排序的特性进行逆序对的计算。而归并排序的具体实现可以参考我之前的详解，传送门放在这啦：

C++实现排序 - 02 归并排序、快速排序和堆排序

我们举个例子，看看具体步骤是如何实现的：

假设我们已经进行到了归并排序中最后一趟合并，通过之前的递归调用，已经得到了两个有序的序列，分别是数组的前后两半部分。然后我们初始化两个指针 i 和 j ，使他们分别指向数组前半部分和数组后半部分的第一个元素。

第一步： 判断两指针指向的元素，发现 nums[i] < nums[j] 即 1 < 2 。此时 i 指向的元素要小于 j 指向的元素，所以不用计算逆序对，直接加入答案数组中即可。

因为 i 指向的这个元素始终是在 j 指向的元素左边，即使排不排序都不会改变两者的相对位置即无法构成一个逆序对。另外，左半部分 1 以后的元素都大于等于 1 ，故无法判断它们与 2 之间的关系，逆序对不能计算。

第二步： 判断两指针指向的元素，发现 nums[i] > nums[j] 即 4 > 2 。此时就要注意了，因为执行完排序后，4 和 2 的相对位置会发生改变，说明 4 和 2 排序前就可以构成逆序对。

另外，由于左半部分数组与右半部分数组只是在各个区间内有序，两部分区间中的元素之间的相对位置并没有发生改变。

所以左半部分中 4 以后的元素 5 和 8 都一定是大于 2 的，并且他们在排序之前都是可以构成逆序对的，故可以得到 `res += mid - i + 1 = 3 - 1 + 1 = 3 。

第三步： 与第二步一样， nums[i] > nums[j] 即 4 > 3 。所以 4 后面的 5 和 8 同样都大于 3 ，他们之间同样可以构成逆序对，故 res += 3 。

第四步： 与第一步一样，nums[i] < nums[j] 即 4 < 6 ，故直接加入答案数组中即可。

第五步： 同样，nums[i] < nums[j] 即 5 < 6 ，故直接加入答案数组中即可。

第七步： nums[i] > nums[j] 即 8 > 6 且 8 后面没有元素了，故 res += 1 。

第八步： nums[i] < nums[j] 即 8 < 9 ，故直接加入答案数组中即可。

第九步： 左半数组已经全部遍历完，故直接将右半数组的剩余部分加入答案数组中，并返回最终计算的逆序对数量 res 即可。

Tips： 可能会有小伙伴担心其中计算的逆序对会不会有重复的部分，其实完全不会。因为归并排序每趟排序中用到的两个数组部分的相对位置都还没有进行改变，每次计算出来的逆序对一定是唯一的。

class Solution {
public:
    //归并排序的过程中计算逆序对个数
    int merge(vector<int>& nums, int l, int r) {
        if (l >= r) return 0;

        int mid = l + r >> 1;
        int res = merge(nums, l, mid) + merge(nums, mid + 1, r);

        vector<int> temp;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (nums[i] <= nums[j])    temp.push_back(nums[i++]);
            else {
                temp.push_back(nums[j++]);
                res += mid - i + 1;
            }
        while (i <= mid)   temp.push_back(nums[i++]);
        while (j <= r) temp.push_back(nums[j++]);

        int k = l;
        for (auto x : temp)    nums[k++] = x;

        return res;
    }

    int inversePairs(vector<int>& nums) {
        return merge(nums, 0, nums.size() - 1);
    }
};

欢迎大家在评论区交流~