问题描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
class Solution {
public:
int InversePairs(vector<int> data) {
int n= data.size();
long long int result;
vector<int> temp=data;
result= merge_sort(data,0,n-1,temp);
return result%1000000007;
}
long long int merge(vector<int> &data,int start,int mid,int end,vector<int> &temp){
int i=start,j=mid+1,k=start;
long cnt=0; //这里很重要
while (i<=mid&&j<=end)
{
if(data[i]>data[j]){
temp[k++]=data[j++];cnt+=mid-i+1;
}
else{
temp[k++]=data[i++];
}
}
while (i<=mid)
{
temp[k++]=data[i++];
}
while (j<=end)
{
temp[k++]=data[j++];
}
for (int i=start;i<=end;i++) //这里忘了将临时数组的值还回去，这样每次白排序了
{
data[i]=temp[i];
}
return cnt;
}
long long int merge_sort(vector<int> &data,int start,int end,vector<int> &temp ){
int mid;
long cnt=0; //这里很重要
if(start==end){
temp[start]=data[start];
}
else{
mid=(start+end)/2;
cnt+=merge_sort(data,start,mid,temp);//这里也要加cnt，每个递归的mergeSort的值都要加起来，为防止错误，最好用全局变量
cnt+=merge_sort(data,mid+1,end,temp);
cnt+=merge(data,start,mid,end,temp);
}
return cnt;
}
};
注意事项
1.一定要注意数字越界。。。。。int 和long我曹溢出了。。。
2.vector的使用
