java简单实现数组中的逆序对
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007
解题思路:
一开始一头雾水,后面想到了使用归并排序的思想,其实有多少个逆序对,就是归并排序的时候,后面的数要超越前面多少个,嗯,好像不是很好说,要不然直接看代码吧。还要注意,题目当中说要输出取模的结果,这说明数据可能非常大,所以如果只是单纯的在最后取模的话可能还是无法避免数据太大的影响,所以我们在每次更新count的时候就对其进行取模运算。
刚好又练习了一遍归并排序,记录一下
publicclassSolution{
intcount;
publicintInversePairs(int[]array){
count=0;
if(array!=null){
divPairs(array,0,array.length-1);
}
returncount%1000000007;
}
publicvoiddivPairs(int[]array,intstart,intend){
if(start>=end)
return;
intmid=(start+end)>>1;
divPairs(array,start,mid);
divPairs(array,mid+1,end);
mergePairs(array,start,mid,end);
}
publicvoidmergePairs(int[]array,intstart,intmid,intend){
inti=start,j=mid+1,k=0;
int[]temp=newint[end-start+1];
while(i<=mid&&j<=end){
if(array[i]<=array[j]){
temp[k++]=array[i++];
}else{
temp[k++]=array[j++];
count+=mid-i+1;
count%=1000000007;
}
}
while(i<=mid){
temp[k++]=array[i++];
}
while(j<=end){
temp[k++]=array[j++];
}
for(intx=0;x
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。 热门推荐
1 训练狗狗搜寻
2 如何训练狗狗装死
3 狗狗训练书
6 怎么训练狗狗拜年
8 狗狗训练游戏
10 狗狗嗅觉训练
11 怎么训练狗狗在笼子里不叫
12 怎么训练狗狗站立走路
13 怎么训练狗狗在马桶上
14 狗狗尿尿怎么训练
15 训练狗狗用品
16 泰迪狗狗的训练方法大小便
17 训练狗狗可以打吗
18 王曼丽的狗狗训练