题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
方法：归并排序
每次合并的时候，后半部分都要与前一部分进行比较，每次比较时出现后一部分值比前一部分大，就可以判断出现了逆序，逆序的大小为m-i+1;
public class Solution {
int count=0;
public int InversePairs(int [] array) {
int l=0,h=array.length;
if(h<2)return 0;
mergeSort(array,l,h-1);
return count;
}
public void mergeSort(int[]arr,int l,int h){
int m=l+(h-l)/2;
if(l<h){
mergeSort(arr,l,m);
mergeSort(arr,m+1,h);
merge(arr,l,m,h);
}
}
public void merge(int[]arr,int l,int m,int h){
int [] temp = new int[h-l+1];
int i=l,j=m+1;
int index=0;
while(i<=m&&j<=h){
if(arr[i]<arr[j])
temp[index++]=arr[i++];
else{
temp[index++]=arr[j++];
count+=m-i+1;//这里一定要是m-i+1而非m-l+1，因为i是动态变化的
count%=1000000007;
}
}
while(i<=m)
temp[index++]=arr[i++];
while(j<=h)
temp[index++]=arr[j++];
for(int k=0;k<temp.length;k++)
arr[k+l]=temp[k];
}
}
360集团公司福利 188人发布
