分治归并求逆序对个数（java)

239 阅读 0 评论 0 点赞

## 思路
分治的思想。
总的逆序数=左子数组的逆序数+右子数组的逆序数+横跨两个有序子数组的数产生的逆序的个数。
### 对于子数组的逆序数：
我们可以递归不断地将数组拆成两半，直到子数组长度为1，长度为1的子数组逆序数就是0；所以我们只需要累加上横跨两个有序子数组的数产生的逆序的个数就行了。
### 对于横跨两个有序子数组的数产生的逆序的个数。
在归并排序的过程中使子数组有序。
在合并两个有序子数组之前，统计横跨两个有序子数组的数产生的逆序的个数。
因为两个子数组都是升序的。逆序对一个出自左子数组，一个出自右子数组。
①如果左子数组中某个元素left[l]>右子数组的某个元素right[r].那么有所以左子数组中l以后的元素都将与right[r]构成逆序对。总的逆序数直接加left.length-l;
②然后r++,直到出现大于left[l]的，在左移l,找到left[l]>right[r],总的逆序数再加left.length-l；
③重复①②步直到l==left.length或r==right.length.因为若是前者，因为right升序，不可能在r+=k后找到left[k]>right[r+k];所以不会有逆序对。而若是后者，说明所有可能逆序对已经判断完了
最终得到的cnt就是总的逆序数。

```java
package algorithm.dongxin;
import java.util.Scanner;
public class ReverseOrderNumber {
    static int[] numArr;
    static int cnt=0;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        numArr=new int[n];
        for (int i=0; i<n;i++)
            numArr[i]=sc.nextInt();
        func(0,n-1);
        System.out.println(cnt);
    }
    static int[] mergeAndCnt(int[] arrl,int[] arrr,int len){//在做归并排序合并两个有序子数组之前记录逆序数。
        int l=0,r=0;
        while(l<arrl.length&&r<arrr.length){
            if(arrl[l]>arrr[r]){
                cnt+=arrl.length-l;
                r++;
            }
            else
                l++;
        }
        l=0;r=0;
        int[] allArr=new int[len];
        int i=0,tag=0;
        while(r<arrr.length){
            if(tag==1)
                break;
            if(arrl[l]<arrr[r]){
                allArr[i++]=arrl[l];
                l++;
            }
            else{
                allArr[i++]=arrr[r];
                r++;
            }
            if(r>=arrr.length){
                for(int j=l;j<arrl.length;j++){
                    allArr[i++]=arrl[j];
                }
                tag=1;
            }
            if(l>=arrl.length){
                for(int j=r;j<arrr.length;j++){
                    allArr[i++]=arrr[j];
                }
                tag=1;
            }
        }
        return allArr;
    }

static int[]  func(int start, int end) {//归并排序的过程
        if(end==start){
            int[] Arr=new int[]{numArr[start]};
            return Arr;
        }
        else{
            int mid=(end+start)/2;
            int[] midArrl=func(start,mid),midArrr=func(mid+1,end);
            return mergeAndCnt(midArrl,midArrr,end-start+1);
        }
    }
}

```

0.0分

1 人评分

本文分类：题解列表
浏览次数：239 次浏览
发布日期：2023-03-11 19:53:43
本文链接：https://blog.dotcpp.com/a/94749

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

分治归并求逆序对个数（java)

评论列表共有 0 条评论

发表评论取消回复

分治归并求逆序对个数（java)

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复