java实现数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对，例如在数组｛7，5，6，4｝中，一共存在5对逆序对，分别是｛7，6｝，｛7，5｝，｛7，4｝，｛6，4｝，｛5，4｝。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。，即输出P%1000000007。
代码
解法一
暴力简单低效，不会改变原数组
publicstaticintinversePairs(int[]array){
if(array==null||array.length<2){
return0;
}
intcount=0;
for(inti=0;iarray[j]){
count++;
}
}
}
returncount%1000000007;
}
解法二
利用数组的归并排序，高效，但是会改变原数组
publicstaticintinversePairs2(int[]array){
if(array==null||array.length<2){
return0;
}
intcount=mergeSort(array,0,array.length-1);
returncount%1000000007;
}
privatestaticintmergeSort(int[]array,intstart,intend){
if(start>=end){
return0;
}
//找到数组的中点，分割为两个子数组，递归求解
intmiddle=(start+end)/2;
intleft=mergeSort(array,start,middle);
intright=mergeSort(array,middle+1,end);
//存储归并后的数组
int[]copy=newint[array.length];
System.arraycopy(array,start,copy,start,end-start+1);
//从两个子数组的尾部开始遍历
inti=middle;
intj=end;
intcopyIndex=end;
//记录逆序对的数量
intcount=0;
while(i>=start&&j>=middle+1){
//数组是升序的
//如果左边数组比右边数组大，则将大的放入存储数组中
//并且累加逆序对，应为是有序的，所以左边数组的第i个元素比第j个及其之前的数都大
if(array[i]>array[j]){
copy[copyIndex--]=array[i--];
count+=(j-middle);
}else{
copy[copyIndex--]=array[j--];
}
}
//将子数组剩余的部分一次写入归并后的存储数组
while(i>=start){
copy[copyIndex--]=array[i--];
}
while(j>=middle+1){
copy[copyIndex--]=array[j--];
}
//将本次两个子数组的合并写入原数组中
for(intk=start;k<=end;k++){
array[k]=copy[k];
}
returnleft+right+count;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。