BM20 数组中的逆序对

约定不等于承诺〃 2023-10-04 17:41 45阅读 0赞

### 描述 ###

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

数据范围： 对于 50\\%50% 的数据, size≤10^4  
对于 100% 的数据,size≤10^5

数组中所有数字的值满足 0 \\le val \\le 10000000≤val≤1000000

要求：空间复杂度O(n)，时间复杂度 O(nlogn)

#### 输入描述： ####

题目保证输入的数组中没有的相同的数字

### 示例1 ###

输入：

[1,2,3,4,5,6,7,0]

返回值：

### 示例2 ###

输入：

[1,2,3]

返回值：

## **方法一** ##

**(暴力)**

public int InversePairs(int [] array) {
            /*
           int len=array.length;
            int cnt=0;
            for(int i=0;i<len-1;i++){
                for(int j=i+1;j<len;j++){
                    if(array[i]>array[j])
                        cnt++;
                }
            }
            return cnt;
    }

## **方法二** ##

**分治法**

问题转化：求逆序对就是统计有多少个前大后小的数对，问题和归并两个有序数组求前大后小数对一样。所以现在的问题变为统计子问题中逆序对的个数。

递归模型变形：递归按照标准的归并排序来，注意的是统计个数，当出现nums\[i\]>nums\[j\]时，**统计所有前半段区间内比nums\[j\]大的数及为cnt+=mid-l+1;**

**由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组进行从小到大的排序  
以免在以后的统计过程中再重复统计。**

![22d4062e20e27f7a7a157c75b77bc75d.png][]

代码：

public class Solution {
        int cnt=0;  //统计逆序对
        //合并
       public void merge(int[] arr,int left,int mid, int right){
            int[] a=new int[right-left+1];
            int t=0;
            int l=left;
            int r=mid+1;
            while(l<=mid&&r<=right){
                if(arr[l]>arr[r]){  //有逆序对，l下标的数后面所有数都大于r下标的数
                    //由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组进行从小到大的排序 
                    //以免在以后的统计过程中再重复统计。
                    a[t++]=arr[r++];
                    cnt=(cnt+mid-l+1)%1000000007;   //mid-l+1 这么多个逆序对，因为arr[l~mid]>arr[r]
                }
                else{
                    a[t++]=arr[l++];
                }
            }
            while(l<=mid){
                a[t++]=arr[l++];
            }
            while(r<=right){
                a[t++]=arr[r++];
            }
            for(int k=0;k<a.length;k++){
                arr[left+k]=a[k];
            }
        }
      public  void mergersort(int[] array, int l,int r){
            if(l>=r)
                return;
            int mid=(r+l)/2;
            //分
            mergersort(array,l,mid);
            mergersort(array,mid+1,r);
            //并
            merge(array,l,mid,r);
        }
        
        public int InversePairs(int [] array) {
            int len=array.length;
            mergersort(array,0,len-1);
            return cnt;
        }
    }

[22d4062e20e27f7a7a157c75b77bc75d.png]: https://img-blog.csdnimg.cn/img_convert/22d4062e20e27f7a7a157c75b77bc75d.png