思路：

题目的主要信息：

• 逆序对：前面的数字比后一个数字大，构成一对逆序对
• 答案可能会非常大，因此用到了取余1000000007
• 不用考虑相同的数字

最能想到思路，莫过于依次比较数组中每两个数，然后统计逆序对的数量。但是既然答案都会非常大了，数据量最大也可能达到$10^{5}10^5$105，依次比较可能会超时。

方法一：暴力法(超时）

具体做法： 两层遍历，依次比较该数与后续其他数的大小关系，统计逆序对数量。 不出意外，这种方法超时了。

class Solution {
public:
    int InversePairs(vector<int> data) {
        int res = 0;
        for(int i = 0; i < data.size(); i++){
            for(int j = i + 1; j < data.size(); j++){
                if(data[i] > data[j]){ //逆序对
                    res++;
                    res %= 1000000007;  //取余防止溢出
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，两层循环
• 空间复杂度：$O\left(1\right)O(1)$O(1)，没有额外空间

方法二：归并排序

统计逆序对就是遇到大的在前小的在后的时候会统计，这种情况我们在排序的时候经常遇到，因此可以使用时间复杂度更低的归并排序思想来解决这个问题。 归并排序有三个步骤：

• 划分：将待排序的区间为 $[left,right][left,\; right]$[left,right]，令 $mid=(left+right)/2mid\; =\; (left\; +\; right)\; /\; 2$mid=(left+right)/2，我们把 $[left,right][left,\; right]$[left,right]分成了$[left,mid][left,\; mid]$[left,mid]和 $[mid+1,right][mid\; +\; 1,\; right]$[mid+1,right]
• 排序： 再次使用归并排序递归地排序两个子序列
• 合并：把两个已经排好序的子序列合并起来

当归并排序中，右边大于左边时，它是大于左右所有子序列的，由这个性质我们可以避免每次统计+1，减少很多运算。

class Solution {
public:
    int mergeSort(int left, int right, vector<int>& data, vector<int>& temp){
        if (left >= right)    // 停止划分条件
            return 0;
        //划分阶段
        int mid = (left + right) / 2;
        int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp);
        // 合并阶段
        res %= 1000000007;  //防止溢出，取余
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++)
            temp[k] = data[k];
        for (int k = left; k <= right; k++) {
            if (i == mid + 1)
                data[k] = temp[j++];
            else if (j == right + 1 || temp[i] <= temp[j])
                data[k] = temp[i++];
            else { //左边比右边大，答案增加
                data[k] = temp[j++];
                res += mid - i + 1; // 统计逆序对
            }
        }
        return res % 1000000007;
    }
    int InversePairs(vector<int> data) {
        vector<int> temp(data.size());
        return mergeSort(0, data.size() - 1, data, temp);
    }
};

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，归并排序的时间复杂度
• 空间复杂度：$O\left(n\right)O(n)$O(n)，辅助数组temp