欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数组中的逆序对

程序员文章站 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]+" ");
        }

    }

}

数组中的逆序对