使用成员变量记录逆序对总数

数组中的逆序对

http://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5

全称都是归并排序的,只是在逆序的情况下(nums[start1]>nums[start2]),需要增加更新逆序对的代码。

很简单,使用成员变量记录逆序对总数。

private int pairs.

...
if(nums[start1]>nums[start2]){
    ...
    pairs+=mid-start1+1;
    pairs%=10000007;
}
...

大佬的图解,来源:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/bao-li-jie-fa-fen-zhi-si-xiang-shu-zhuang-shu-zu-b/
图片说明

    /**
     * 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。
     * 输入一个数组,求出这个数组中的逆序对的总数P。
     * 并将P对1000000007取模的结果输出。 即输出P%1000000007
     * @param array 数组
     * @return 数组中的逆序对的总数P
     */
    public int InversePairs(int [] array) {
        if(array==null||array.length<2){
            return 0;
        }
        int[] aux=new int[array.length];
        InversePairs(array,aux,0,array.length-1);
        return this.pairs;
    }
    private int pairs;
    public void InversePairs(int[] nums,int[]aux,int left,int right){
        if(left<right){

            int mid=left+(right-left)/2;
            InversePairs(nums,aux,left,mid);
            InversePairs(nums,aux,mid+1,right);
            merge(nums,aux,left,mid,right);
        }




    }
    public void merge(int[] nums,int[] aux,int left,int mid,int right) {
        //标准的merge过程,当逆序时,格式为mid-i+1,相当于(mid与i之间的数量)
        int start1 = left, end1 = mid, start2 = mid + 1, end2 = right;
        int k = left;
        while (start1 <= end1 && start2 <= end2) {
            //存在逆序对
            if (nums[start1] > nums[start2]) {
                aux[k++] = nums[start2++];
                this.pairs += (mid - start1 + 1);
                this.pairs %= 1000000007;
            } else {
                aux[k++] = nums[start1++];
            }
        }
        while (start1 <= end1) {
            aux[k++] = nums[start1++];
        }
        while (start2 <= end2) {
            aux[k++] = nums[start2++];
        }
        for (int i = left; i <= right; i++) {
            nums[i] = aux[i];
        }
    }
全部评论

相关推荐

喜欢吃蛋糕仰泳鲈鱼是我的神:字节可以找个hr 给你挂了,再放池子捞
点赞 评论 收藏
分享
我见java多妩媚:大外包
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务