【归并】数组中的逆序对

求解代码

intmod=1000000007;longmergeSort(int[]nums,intleft,intright){if(left>=right){return0;}intmid=left+((right-left)>>1);// 分治计算左右区间，并立即取模longres=(mergeSort(nums,left,mid)+mergeSort(nums,mid+1,right))%mod;int[]temp=newint[right-left+1];inti=left;intj=mid+1;intk=0;while(i<=mid&&j<=right){// 严格判断nums[i] <= nums[j]，仅大于时统计逆序对if(nums[i]<=nums[j]){temp[k++]=nums[i++];}else{temp[k++]=nums[j++];// 累加后立即取模，防止溢出res=(res+mid-i+1)%mod;}}// 拷贝左区间剩余元素while(i<=mid){temp[k++]=nums[i++];}// 拷贝右区间剩余元素while(j<=right){temp[k++]=nums[j++];}// 覆盖回原数组for(k=0,i=left;k<temp.length;k++,i++){nums[i]=temp[k];}returnres;}publicintInversePairs(int[]nums){if(nums==null||nums.length<=1){return0;}return(int)(mergeSort(nums,0,nums.length-1)%mod);}