思路：歸并排序
每次把數(shù)組從中間拆分成兩部分，先統(tǒng)計拆分數(shù)組內(nèi)部的逆序?qū)?，再把這個數(shù)組排序，防止統(tǒng)計重復，最后再把拆分的數(shù)組合并，并統(tǒng)計合并過程中的逆序?qū)Α?br>
Paste_Image.png
Paste_Image.png
public int InversePairs(int [] array) {
if(array==null||array.length==0)
return 0;
int[] copy = new int[array.length];
for (int i = 0; i < copy.length; i++) {
copy[i] = array[i];
}
int count = InversePairsHelper(array, copy, 0, array.length - 1);
return count;
}
public int InversePairsHelper(int [] array,int [] copy,int start,int end) {
if(start==end){
copy[end]=array[end];
return 0;
}
int len=(end-start)/2;//
int left=InversePairsHelper(array,copy,start,start+len);
int right=InversePairsHelper(array,copy,start+len+1,end);
int i=start+len;
int j=end;
int indexofCopy=end;
while(i>=start&&j>start+len+1){
if(array[i]>array[j]){
copy[indexofCopy--]=array[i--];
count+=j-start-len;
}else{
copy[indexofCopy--]=array[j--];
}
}
for(;i>=start;i--){
copy[indexofCopy--]=array[i--];
}
for(;j>=start+len+1;j--){
copy[indexofCopy--]=array[i--];
}
return left+right+count;
}
