剑指Offer_51 求逆序对数

题目：

在数中的两个数组，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。例如，在数组{7,5,6,4}中，一共存在5个逆序对，分别是（7，6），（7,5），（6,4），（7,4），（5,4）；

思路：采用归并排序，将两个小的数组合并成一个有序的大数组，并且将新的合并有序数组作为源数据，继续归并。

分析：

class Solution{

    public static int reversePairs(int [] nums,int length){
        if(nums==null||nums.length==0){
            return 0;
        }
        //赋值新的数组
        int [] copy= Arrays.copyOf(nums,nums.length);

        return reversePairsCore(nums,copy,0,length-1);
    }
    public static int reversePairsCore(int [] data,int [] copy,int start,int end){
        if(start==end){
            copy[start]=data[start];
            return 0;
        }

        int length=(end-start)/2;
        //归并,互换了新的源数据数组更改为copy了
        int left=reversePairsCore(copy,data,start,start+length);
        int right=reversePairsCore(copy,data,start+length+1,end);
        //初始化为前半段最后一个数字的下表
        int i=start+length;
        //初始化后半段最后一个数字的下表
        int j=end;

        //辅助数组的最后一个下表
        int indexCopy=end;

        int count=0;
        while (i>=start&&j>=start+length+1){
            if(data[i]>data[j]){
                copy[indexCopy--]=data[i--];
                //小的那个数在第几个位置，那么前面均可以组成为逆序数对
                count+=j-start-length;
            }else{
                copy[indexCopy--]=data[j--];
            }
        }

        //防止还有数组
        for(;i>=start;i--){
            copy[indexCopy--]=data[i];
        }
        for(;j>=start+length+1;j--){
            copy[indexCopy--]=data[j];
        }

        return left+count+right;
    }
}

最后

以上就是烂漫鲜花为你收集整理的剑指Offer_51 求逆序对数的全部内容，希望文章能够帮你解决剑指Offer_51 求逆序对数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。