剑指offer 数组中的逆序对

题目描述

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

输入描述:

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

数据范围：

对于P的数据,size<=10^4

对于u的数据,size<=10^5

对于0的数据,size<=2*10^5

示例1

输入

复制 1,2,3,4,5,6,7,0

输出

复制 7

代码：

class Solution { public: int InversePairs(vector<int> data) { if(data.size()==0)return 0; vector<int>copy(data); return merge(data,copy,0,data.size()-1); } int merge(vector<int>&data,vector<int>©,int l,int r){ //因为copy数组和data数组传递的是引用，而内层的遍历都需要把copy数组排好序， //自然而然，上一层的data数组就排好序了，所以返回上一层时可以直接使用了 if(l==r)return 0; int mid=(r+l)/2; int left=merge(copy,data,l,mid); //注意，这里copy和data交换了顺序，所以内层遍历中copy数组会排好序从而导致返回外层时data数组排好序 int right=merge(copy,data,mid+1,r); int i=mid; int j=r; int end=r; long count=0;//设成int型只能通过50%的数据 while(i>=l&&j>=mid+1){ if(data[i]>data[j]){ count+=j-mid; copy[end--]=data[i--]; }else{ copy[end--]=data[j--]; } } while(i>=l) copy[end--]=data[i--]; while(j>=mid+1) copy[end--]=data[j--]; return (left+right+count)00000007; } };