很巧的一道题，中午刚刚复习了排序算法
使用归并排序的思想
另一种方法就是暴力for循环
public class Solution {
int count =0;
public int InversePairs(int [] array) {
merge(array,0,array.length-1);
return count;
}
public void merge(int[] arg,int left,int right){
if(left>=right) return;
int mid = left+((right-left)>>1);//防止溢出
merge(arg,left,mid);
merge(arg,mid+1,right);
mergeSort(arg,left,mid,right);
}
public void mergeSort(int[] arg,int left,int mid,int right){
int p1 = mid,p2=right;
int p=right-left;
int[] result = new int[right-left+1];
while(p1>=left&&p2>mid){
if(arg[p1]>arg[p2]){
result[p--] = arg[p1];
count+=p2-mid;
if(count>=1000000007){
count%=1000000007;
}
p1--;
}else{
result[p--] = arg[p2];
p2--;
}
}
for(;p1>=left;p1--){
result[p--] = arg[p1];
}
for(;p2>mid;p2--){
result[p--] = arg[p2];
}
for(int i = 0;i<result.length;i++){
arg[left+i] = result[i];
}
}
}
