描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

数据范围：  对于 50\%50% 的数据, size\leq 10^4size≤104
对于 100\%100% 的数据, size\leq 10^5size≤105
数组中所有数字的值满足 0 \le val \le 10000000≤val≤1000000

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

输入描述：

题目保证输入的数组中没有的相同的数字

示例1

输入： 
[1,2,3,4,5,6,7,0]
复制
返回值： 
7
复制

示例2

输入： 
[1,2,3]
复制
返回值： 
0
复制

解题思路
1、首先想到的是暴力解法，但是暴力解法的时间复杂度是O(N*N)，不符合题目要求；
2、O(nlogn)的时间复杂度一般是二分查找，本题中不是查找最优解，儿时统计逆序对个数；
3、仔细分析题意，找逆序对的过程可以用归并排序的过程来实现；
4、先将无序数组递归的二分为一个一个的数，再通过比较大小的方式将单个的数一块一块并起来，再并的过程中排序，同时统计逆序个数；
5、需要特别注意的是，merge函数中，已经可以认为左右区间已经分别有序，从左右的其实点开始遍历时，若遇到逆序对，那么对于左区间上其余值来说也一定是逆序对； 



class Solution {
public:
    // 暴力解法会超时
    /*int InversePairs(vector<int> data) {
        int n = data.size();
        int res = 0;
        for (int i = n - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (data[j] > data[i]) {
                    res++;
                    if (res == 1000000007) res = 0;
                }
            }
        }
        return res;
    }*/
    int merge(vector<int> &data, int left, int mid, int right, vector<int> &tmp) {
        // 左半区未排序元素索引
        int l_pos = left;
        // 右半区未排序元素索引
        int r_pos = mid + 1;
        // 临时数组索引
        int pos = left;
        int res = 0;

        // 合并
        // 此时的左右部分已经分别有序了
        while (l_pos <= mid && r_pos <= right) {
            if (data[l_pos] > data[r_pos]) {
                tmp[pos++] = data[r_pos++];
                //res++;
                // 出现左侧大于右侧的情况后，左侧索引之后的所有数字肯定都是大于右侧当前数字的。故需要加的是左侧从当前索引开始到最后位置的数字个数，同时右侧索引移到下一位
                res += mid + 1 - l_pos;
                res = res % 1000000007;
            } else {
                tmp[pos++] = data[l_pos++];
            }
        }

        while (l_pos <= mid) {
            tmp[pos++] = data[l_pos++];
            
        }
        while (r_pos <= right) {
            tmp[pos++] = data[r_pos++];
        }
        for (int i = left; i <= right; i++) {
            data[i] = tmp[i];
        }
        return res;
    }
    // 计算left到right之间有几个逆序对
    int div(vector<int> &data, int left, int right, vector<int> &tmp) {
        int mid = (right - left) / 2 + left;
        int res = 0;
        if (left >= right) {
            return res;
        }
        res += div(data, left, mid, tmp);
        res = res % 1000000007;
        res += div(data, mid+1, right, tmp);
        res = res % 1000000007;
        res += merge(data, left, mid, right, tmp);
        res = res % 1000000007;
        return res;

    }
    int InversePairs(vector<int> data) {
        int n = data.size();
        int res = 0;
        if (n < 2) return 0;
        vector<int> tmp(n);        
        res = div(data, 0, n-1, tmp);
        return res;
    }
};