题解 | #数组中的逆序对#

题目主要信息:

• 在数组中，如果有位置靠前的一个数字大于位置靠后的一个数字，则这两个数字构成一个逆序对
• 题目输入一个无重复数字的数组，需要求这个数组中共有多少逆序对
• 结果需要对1000000007取模

具体思路:

遍历数组每个数字，然后去查看它后面的所有数字是不是还有比它小的，然后统计个数，这样肯定不现实，会超时。这说明逐个统计不可行，有没有一种可能让我们一次性可以统计多个？

逆序逆序，让我们可以想到排序将逆序去掉，什么排序方法与逆序对的交换最相关呢，大概就是归并排序了。因为我们在归并排序过程中会将数组划分成最小2个元素的子数组，然后依次比较子数组的长度，这里我们也可以用相同的方法统计逆序对。因为在归并排序中，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。

• step 1：划分阶段，将待划分区间从中点划分成两部分。
• step 2：排序阶段，使用归并排序递归地处理子序列，同时统计逆序对。
• step 3：合并阶段，将排好序的子序列合并。

统计过程可以参考如下图示：

代码实现:

class Solution {
public:
    int mod = 1000000007;
    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 %= mod;  //防止溢出
        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 % mod;
    }
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> res(n);
        return mergeSort(0, n - 1, data, res);
    }
};

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，归并排序利用分治思想
• 空间复杂度：$O(n)O(n)$，辅助数组及递归栈的长度