一、题目描述

题目大意：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
注意审题：前面一个数字要严格大于后面的数字，且要对结果取模

二、算法1（暴力）

解题思路

依次检查当前每个数与其前面的数形成的逆序对的个数，两重for循环，时间复杂度，对于本题的数据范围显然会超时

代码实现（C++11）

class Solution {
private:
    static constexpr int mod = 1e9 + 7;
public:
    int InversePairs(vector<int> data) {
        int n = data.size();
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (data[j] > data[i]) {    // data[j] > data[i]
                    ++cnt;
                    cnt %= mod;
                }
            }
        }
        return cnt;
    }
};

时间复杂度：，n为数组的长度，两重循环时间复杂度为，超时
空间复杂度：，使用常数空间

三、算法2（归并排序）

解题思路

  1. 归并排序求逆序对是非常经典的做法，一定要掌握并理解。归并排序采用了分而治之的思想，将大区间求逆序对的问题转换为小区间求逆序对的问题，而优于暴力做法的地方在于归并排序能更快地求出一个数前面比它大的数的个数
  2. 归并排序将数组一分为二，假设数组为[1, 3, 4, 2]， 分离后就是[1, 3]和[4, 2]，那么[1, 3, 4, 2]的逆序对个数为区间[1, 3]的逆序对个数 + 区间[4, 2]的逆序对的个数 + 跨越区间的逆序对个数；这就到了归并排序上场的时候了，归并排序‘并’的过程实质上就是将两个有序的子数组合并为一个有序的数组，假设这两个子区间自身的逆序对已经通过递归求出来了，那么跨越这两个区间的逆序对个数怎么求呢。很简单，由于两个子区间都是有序的，因此只要使用双指针同时遍历，当遇到左区间中的一个数a[i]大于右区间的数a[j]时，可知对于a[j]来说，跨越区间的逆序对个数应该为mid - i + 1，mid为左区间的右边界，因为i后面的数一定不小于a[i]，这样我们就能够快速地求出a[j]对逆序对的贡献了，自底向上递归即可得到最终的逆序对数

图片说明

代码实现（C++11）

class Solution {
private:
    static constexpr int mod = 1e9 + 7;    
public:
    int cnt = 0;
    vector<int> tmp;

    int InversePairs(vector<int> data) {
        int n = data.size();
        tmp.resize(n);
        merge_sort(data, 0, n - 1);
        return cnt;
    }

    void merge_sort(vector<int>& data, int l, int r) {
        if (l >= r) return;              // 边界处理（只有一个数或没有）
        int mid = l + r >> 1;
        merge_sort(data, l, mid);        // 向左递归
        merge_sort(data, mid + 1, r);    // 向右递归

        int i = l, j = mid + 1, k = l;
        while (i <= mid && j <= r) {
            if (data[i] <= data[j]) tmp[k++] = data[i++];
            else {    // 找到左区间一个数a[i] > a[j]
                tmp[k++] = data[j++];
                cnt += mid - i + 1;    // 此时区间[i, mid]的数都大于data[j]
                cnt %= mod;
            }
        }

        while (i <= mid) tmp[k++] = data[i++];    // 左区间有剩余
        while (j <= r) tmp[k++] = data[j++];      // 右区间有剩余

        for (int i = l; i <= r; i++) data[i] = tmp[i];    // 拷贝回data数组
    }
};

时间复杂度：，n为数组的长度，归并排序的时间复杂度为
空间复杂度：，使用了辅助数组tmp，空间复杂度为，递归栈空间为，总空间复杂度为