数组中的逆序对
程序员文章站
2022-06-16 11:03:36
...
public class Solution {
public int count=0;
//方法一、暴力**
public int InversePairs(int [] array) {
if(array==null||array.length==0){
return 0;
}
int p=0;
for(int i=0;i!=array.length;i++){
for( int j=i+1;j!=array.length;j++)
{
if(array[i]>array[j]){
++p;
p=p%1000000007;
}
}
}
return p%1000000007;
}
//方法二:归并排序的思想
public int InversePairs2(int [] array) {
if(array==null||array.length==0){
return 0;
}
Mainmerge(array,0,array.length-1);
return count%1000000007;
}
//递归调用归并函数的主体
public void Mainmerge(int[]arr,int start,int end){
if(start>=end){
return;
}
int mid=start+(end-start)/2;
Mainmerge(arr,start,mid);
Mainmerge(arr,mid+1,end);
merge(arr,start,mid,end);
}
//合并函数
public void merge(int[]array,int start,int mid,int end){
int[]tmp=new int[end-start+1];
int i=start,j=mid+1,k=0;
while(i<=mid&&j<=end){
if(array[i]<=array[j])
{
tmp[k++]=array[i++];
}else{
tmp[k++]=array[j++];
count+=mid-i+1;
if(count>1000000007){
count=count%1000000007;
}
}
}
while(i<=mid)
{
tmp[k++]=array[i++];
}
while(j<=end){
tmp[k++]=array[j++];
}
//将已排好序的数组拷贝到原数组
for(k=0;k!=tmp.length;k++){
array[start+k]=tmp[k];
}
}
public static void main(String[]args){
//System.out.println("Hello");
// int i=1000000007;
// System.out.println(i);
// System.out.println(Integer.MAX_VALUE);
int[]arr={1,2,3,4,5,6,7,0};
Solution s=new Solution();
System.out.println(s.InversePairs2(arr));
for(int i=0;i!=arr.length;i++)
{
System.out.print(arr[i]+" ");
}
}
}