每日一题《剑指offer》数组篇之数组中的逆序对

终有救赎

发布于 2023-10-16 10:22:52

3550

文章被收录于专栏：多线程多线程

今日题目链接: 数组中的逆序对

数组中的逆序对

难度：中等

描述

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

数据范围

对于 50%的数据, size≤104

对于 100%的数据,size≤105

数组中所有数字的值满足 0≤val≤109

举例

解题思路

因为我们在归并排序过程中会将数组划分成最小为1个元素的子数组，然后依次比较子数组的每个元素的大小，依次取出较小的一个合并成大的子数组。

//取中间
int mid = (left + right) / 2; 
//左右划分合并
merge(divide(left, mid, data, temp), divide(mid + 1, right, data, temp));

这里我们也可以用相同的方法划分，划分之后相邻一个元素的子数组就可以根据大小统计逆序对，而不断往上合并的时候，因为已经排好序了，我们逆序对可以往上累计。我们主要有以下三个阶段。

step 1：划分阶段：将待划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为1.
step 2：排序阶段：使用归并排序递归地处理子序列，同时统计逆序对，因为在归并排序中，我们会依次比较相邻两组子数组各个元素的大小，并累计遇到的逆序情况。而对排好序的两组，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。
step 3：合并阶段：将排好序的子序列合并，同时累加逆序对。

实现代码(java)

public class Solution {
    public int mod = 1000000007;
    public int mergeSort(int left, int right, int [] data, int [] temp){
        //停止划分
        if(left >= right)    
            return 0;
        //取中间
        int mid = (left + right) / 2; 
        //左右划分合并
        int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); 
        //防止溢出
        res %= mod;  
        int i = left, j = mid + 1;
        for(int k = left; k <= right; k++)
            temp[k] = data[k];
        for(int k = left; k <= right; k++){
            if(i == mid + 1)
                data[k] = temp[j++];
            else if(j == right + 1 || temp[i] <= temp[j])
                data[k] = temp[i++];
            //左边比右边大，答案增加
            else{ 
                data[k] = temp[j++];
                // 统计逆序对
                res += mid - i + 1; 
            }
        }
        return res % mod;
    }
    public int InversePairs(int [] array) {
        int n = array.length;
        int[] res = new int[n];
        return mergeSort(0, n - 1, array, res);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-10-12，如有侵权请联系 cloudcommunity@tencent.com 删除

int