🍍每日推荐
🍖文章开始之前我想首先介绍一下牛客,以便没有使用过的小伙伴能够快速入手,牛客网是国内最大的算法、面试、招聘网站,涵盖了多种大厂面试真题以及题解,里面大佬云集,各种题目的解决方案层出不穷,绝对能让你大开眼界,而且牛客是你在人生中不同的阶段都能对你有所帮助的编程软件(完全免费),如果感兴趣可以访问注册一下
访问链接:牛客-国内最大的刷题网站
问题转化:求逆序对就是统计有多少个前大后小的数对,问题和归并两个有序数组求前大后小数对一样。所以现在的问题变为统计子问题中逆序对的个数。
递归模型变形:递归按照标准的归并排序来,注意的是统计个数,当出现nums[i]>nums[j]时,统计所有前半段区间内比nums[j]大的数及为ans+=m-i+1;(为了理解方便lm前半段,m+1r后半段)
边界注意:
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);
}
}
🍍每日推荐
访问链接:牛客-国内最大的刷题网站