题目描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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，那就可以用归并排序来解决了。
- 正常写一个归并排序。
- 在归并排序组合排序过程时，会把两子区间数据依次比较，重构新的顺序；此时如果左侧数值A大于右侧数值B，那就可以直接把A到中间位置C的数据个数直接累加。因为子区间已经完成排序，既然A都大于B了，那A到C之间所有的数据也必然大于B，所以可构成逆序对。
- 这样操作下来，时间复杂度满足题目要求了。
测试代码：
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; } };
