正文
题目
题解
归并排序得结果
问题转化：求逆序对就是统计有多少个前大后小的数对，问题和归并两个有序数组求前大后小数对一样。所以现在的问题变为统计子问题中逆序对的个数。
递归模型变形：递归按照标准的归并排序来，注意的是统计个数，当出现nums[i]>nums[j]时，统计所有前半段区间内比nums[j]大的数及为ans+=m-i+1;（为了理解方便lm前半段，m+1r后半段）
边界注意：
- i == r+1当前半段已经统计完，剩下后半段归并，证明j后的数都是比nums[m]大的，无需统计
- j == l+1当后半段统计完，剩下前半段归并，i后的数都比num[l]大，但在之前已经统计个数，无需统计 alt
public class Solution { int[] nums,temp; public int merge_sort(int l,int r){ if(l>=r)return 0; int m, i, j, k; long res; m = (l+r)/2; res = (merge_sort(l,m)+merge_sort(m+1,r))%1000000007; //merge for(k=l;k<=r;k++)temp[k]=nums[k]; i = l;j = m+1;k = l; for(k=l;k<=r;k++){ if(i==m+1)nums[k]=temp[j++]; else if(j==r+1||temp[i]<=temp[j])nums[k] = temp[i++]; else { res=(res + m-i+1)%1000000007; nums[k]=temp[j++]; } } return (int)res; } public int InversePairs(int [] array) { nums = array; temp = new int[array.length]; return merge_sort(0,array.length-1); } }
