【原】剑指offer(C++)-JZ51：数组中的逆序对(算法-排序)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围：  对于 50% 的数据,size≤104
对于100% 的数据, size≤105

数组中所有数字的值满足 0≤val≤109

要求：空间复杂度 O(n)，时间复杂度O(nlogn)

示例：

输入：

[1,2,3,4,5,6,7,0]

返回值：

7

解题思路：

本题常规解题思路就是暴力法，但是本题要求复杂度为nlogn，那就可以用归并排序来解决了。

1. 正常写一个归并排序。
2. 在归并排序组合排序过程时，会把两子区间数据依次比较，重构新的顺序；此时如果左侧数值A大于右侧数值B，那就可以直接把A到中间位置C的数据个数直接累加。因为子区间已经完成排序，既然A都大于B了，那A到C之间所有的数据也必然大于B，所以可构成逆序对。
3. 这样操作下来，时间复杂度满足题目要求了。

测试代码：

class Solution {
public:
    int mod = 1000000007;
    // 归并排序
    int mergeSort(vector<int>& data, int left, int right){
        // 停止
        if(left >= right)
            return 0;
        // 中间位
        int mid = (left + right) / 2;
        // 拆分合并，累加逆序对数量
        int count = mergeSort(data, left, mid) + mergeSort(data, mid + 1, right);
        count %= mod;
        // 排序
        int i = left, j = mid + 1;
        vector<int> temp(data);
        for(int t = left; t <= right; ++t){
            // i如果到了mid+1，说明左子区间遍历完毕，后续直接取右区间数据即可
            if(i == mid + 1){
                data[t] = temp[j];
                j++;
            }
            // j如果到了right+1，说明右子区间遍历完毕，后续直接取左区间数据即可
            // 如果左侧值小于右侧值，不符合逆序对，正常排序即可
            else if(j == right + 1 || temp[i] <= temp[j]){
                data[t] = temp[i];
                i++;
            }
            // 如果左侧值大于右侧值，说明左侧当前位置到左子区间结束的数值，都大于该右侧值，直接计算数量：mid-i+1；然后正常排序
            // 这样操作降低了时间复杂度
            else{
                data[t] = temp[j];
                j++;
                count += mid - i + 1;
            }
        }
        return count % mod;
    }
    // 逆序对
    int InversePairs(vector<int>& nums) {
        int size = static_cast<int>(nums.size());
        int count = mergeSort(nums, 0, size - 1);
        return count;
    }
};