前言

如果你恰巧看到了我的上一篇总结《排序算法系列之（七）——分分合合的归并排序》会发现我把搁置了3年半的排序系列又续更了，起因是最近刷题时遇到了逆序对数求解，而解这类问题常用的方法之一就是归并排序，究竟是怎样的一道题呢？我们可以先试着解决一下。

逆序对数

题目非常简短，描述内容如下：

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

示例 1:

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

限制：

1	0 <= 数组长度 <= 50000

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

求解过程

题目要求不难理解，即使你不知道什么是逆序对也能很容易的根据描述写出下面暴力的解法：

class Solution {
    int ans = 0;
public:
    int reversePairs(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] > nums[j]) ++ans;
            }
        }
        return ans;
    }
};

不出意外的获得了 TLE，看看限制范围也能猜到这题暴力肯定不让过，如果数组长度小于 100 还可以考虑搏一搏，而这道题必须用更巧妙的方法才行，而归并排序就是解法之一：

class Solution {
    int ans = 0;
public:
    void mergeCnt(vector<int>& v, int left, int right, vector<int>& t) {
        if (left >= right) return;
        int i = left, mid = (left+right) / 2, j = mid + 1, k = 0;

        mergeCnt(v, left, mid, t);
        mergeCnt(v, mid+1, right, t);

        while(i <= mid && j <= right) {
            if (v[i] <= v[j]) t[k++] = v[i++];
            else {
                t[k++] = v[j++];
                ans += mid - i + 1; // 相比归并排序只多了这一行
            }
        }

        while (i <= mid) t[k++] = v[i++];
        while (j <= right) t[k++] = v[j++];

        copy(t.begin(), t.begin() + right - left + 1, v.begin() + left);
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> t(n);
        mergeCnt(nums, 0, n-1, t);
        return ans;
    }
};

相比原始的归并排序只增加了一行代码，就得到了一个优于暴力解法O(N^2)的O(NlogN)的解法，具体解释可以去看相关题解，本文的总结目的不是解一道题，而是想给自己保留一个有趣的解题目录。

解题目录

刷题大计最近两年断断续续的在进行着，题解也有写过一些，尝试过多种方式，内容比较零散，复习时比较头疼，没有一个完整的大纲和复习线路，所以打算单开一篇总结，持续收集一些有意思的题目，方便后续的复习和拿来即用。

题目的标签主要有两个方面，一是本身的题目知识点类型，另一种是解题用到的解法类型，比如上面提到的这道题，从题目看归为逆序对数，从解法看可以归为排序解法和离散化树状数组解法，所以后面可以会看到一个题目出现在多个目录中的情况，只是分类依据不同而已。

题目分类

逆序对数

51. 数组中的逆序对

解法分类

Trie树

动态规划

19. 秋叶收藏集

……持续补充

总结

有时看似无关的两件事居然关系紧密，比如归并排序加一行代码就可以求解逆序对数
分类、总结、重新分类，在不断分类中重新认识这个世界

==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==

不积跬步，无以至千里；不积小流，无以成江海。放眼于未来，着眼于脚下，一味计划而不行动，最终醒来只会发现是梦一场~

2022-10-5 00:49:14

前言

逆序对数

求解过程

解题目录

题目分类

逆序对数

解法分类

归并排序

离散化树状数组

差分数组

滑动窗口

Trie树

动态规划

总结