【牛客刷题】BM20 数组中的逆序对

傷城~ 2024-05-06 09:44 73阅读 0赞

#### 文章目录 ####

*  题目
 *  题解
 *   *  归并排序得结果
     *  题解代码

> ?每日推荐
> 
> ?文章开始之前我想首先介绍一下[牛客][Link 1]，以便没有使用过的小伙伴能够快速入手，[牛客网][Link 1]是国内最大的算法、面试、招聘网站，涵盖了多种大厂面试真题以及题解，里面大佬云集，各种题目的解决方案层出不穷，绝对能让你大开眼界，而且[牛客][Link 1]是你在人生中不同的阶段都能对你有所帮助的编程软件（完全免费），如果感兴趣可以访问注册一下
> 
> 访问链接：[牛客-国内最大的刷题网站][Link 1]

## 题目 ##

![在这里插入图片描述][62216d7864fa41da9ce64943bf22334c.png]

## 题解 ##

### 归并排序得结果 ###

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

递归模型变形：递归按照标准的归并排序来，注意的是统计个数，当出现nums\[i\]>nums\[j\]时，统计所有前半段区间内比nums\[j\]大的数及为ans+=m-i+1;（为了理解方便lm前半段，m+1r后半段）

边界注意：

*  i == r+1当前半段已经统计完，剩下后半段归并，证明j后的数都是比nums\[m\]大的，无需统计
 *  j == l+1当后半段统计完，剩下前半段归并，i后的数都比num\[l\]大，但在之前已经统计个数，无需统计 alt  
    ![在这里插入图片描述][800c4d3ebaa543bc903b70079aee051f.png]

public class Solution {
        
         
        int[] nums,temp;
       
        public int merge_sort(int l,int r){
        
            if(l>=r)return 0;
            int m, i, j, k;
            long res;
             
            m = (l+r)/2;
            res = (merge_sort(l,m)+merge_sort(m+1,r))%1000000007;
             
            //merge
            for(k=l;k<=r;k++)temp[k]=nums[k];
            i = l;j = m+1;k = l;
            for(k=l;k<=r;k++){
        
                if(i==m+1)nums[k]=temp[j++];
                else if(j==r+1||temp[i]<=temp[j])nums[k] = temp[i++];
                else {
        
                    res=(res + m-i+1)%1000000007;
                    nums[k]=temp[j++];
                }
            }
            return (int)res;
        }
        
        public int InversePairs(int [] array) {
        
            nums = array;
            temp = new int[array.length];
            return merge_sort(0,array.length-1);
        }
    }

### 题解代码 ###

![在这里插入图片描述][f5009393c01b4a0ba62f25362ee0ce35.png]

> ?每日推荐
> 
> 访问链接：[牛客-国内最大的刷题网站][Link 1]

[Link 1]: https://www.nowcoder.com/exam/oj?page=1&tab=SQL%E7%AF%87&topicId=199&fromPut=pc_csdncpt_ddssyx_sql
[62216d7864fa41da9ce64943bf22334c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/a32bf6c233b14327af7c4c74a9fd715d.png
[800c4d3ebaa543bc903b70079aee051f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/c3e3e1367fec473aab5221ada71859e1.png
[f5009393c01b4a0ba62f25362ee0ce35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/ecc24878714142ed8618193aa985c2bb.png