一、题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制:

0 <= 数组长度 <= 50000

二、题目解析

这道题目首先得掌握归并排序的基础知识

1、分解(Divide):将 n 个元素分成个含 n / 2 个元素的子序列。

2、解决(Conquer):用合并排序法对两个子序列递归的排序。

3、合并(Combine):合并两个已排序的子序列已得到排序结果。

而在第二步解决的过程中,不断的通过比较的方式合并两个排序数组,在这个操作中,如果遇到 左子数组当前元素 > 右子数组当前元素,意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。

比如 4 与 2 进行比较,4 > 2,它们是一组逆序对,又因为黄色区域从左到右是递增的,那也就意味着从 start1 到 end1 所有的元素都大于了 2,都和 2 构成了逆序对。

所以,我们只需要在归并排序的代码上添加一行统计逆序对的代码就行。

为了帮助你更好的理解整个过程,我特意做了一组动画,点开可以查看

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 51. 数组中的逆序对: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/
class Solution {

    // 记录逆序对的数量
    private int count;

    public int reversePairs(int[] nums) {

        // 初始化为 0
        count = 0 ;

        int[] result = new int[nums.length];

        // 通过归并排序的方式,不断的记录逆序对的数量
        merge_sort_recursive(nums,result,0,nums.length - 1);

        return count;

    }

    public void merge_sort_recursive(int[] arr, int[] result, int start, int end) {

        // 1、分解到最小需要解决的地步,无法再分解了
        if (start >= end){
            // 需要开始解决问题
            return;
        }

        // 2、解决

        // 计算数组 arr 的中间位置    
        int mid = (start + end ) / 2;

        // start1 为左区间的开始位置
        int start1 = start;

        // end1 为左区间的结束位置
        int end1 = mid;

        // start2 为右区间的开始位置
        int start2 = mid + 1;

        // end2 为右区间的结束位置
        int end2 = end;

        // 调用 merge_sort_recursive 函数,将 arr 数组中的 start1 到 end1 这一区间的数字排序后,并存放到 result 中
        merge_sort_recursive(arr, result, start1, end1);

        // 调用 merge_sort_recursive 函数,将 arr 数组中的 start2 到 end2 这一区间的数字排序后,并存放到 result 中
        merge_sort_recursive(arr, result, start2, end2);

        // 3、合并

        // 将左右区间中较小的数字存放到 result 中,从 k 开始
        int k = start;

        while (start1 <= end1 && start2 <= end2){
            // 如果 arr[start1] < arr[start2])
            if(arr[start1] <= arr[start2]){
                // result[k] 存放的是 arr[start1]
                result[k] = arr[start1] ;
                start1++;
                k++;
            }else{
                // 否则,result[k] 存放的是 arr[start2]
                result[k] = arr[start2] ;

                // 在这里统计逆序对
                count += (end1 - start1 + 1);

                start2++;

                k++;
            }

        }

        // 如果左区间中还有元素,那么把它都添加到 result 中
        while (start1 <= end1){
            result[k] = arr[start1];
            k++;
            start1++;
        }

        // 如果右区间中还有元素,那么把它都添加到 result 中
        while (start2 <= end2){
            result[k] = arr[start2];
            k++;
            start2++;
        }

        // 最后,把结果赋值到 arr 中
        for (k = start; k <= end; k++)
            arr[k] = result[k];
    }

}

2、C++ 代码

3、Python 代码

class Solution:

    # 记录逆序对的数量
    # 初始化为 0
    count = 0 

    def reversePairs(self, nums: List[int]) -> int:

        result = [0] * len(nums)

        # 通过归并排序的方式,不断的记录逆序对的数量
        self.merge_sort_recursive(nums,result,0,len(nums) - 1)

        return self.count


    def merge_sort_recursive(self, arr:List[int], result:List[int], start, end) :

        # 1、分解到最小需要解决的地步,无法再分解了
        if start >= end : 
            # 需要开始解决问题
            return

        # 2、解决

        # 计算数组 arr 的中间位置    
        mid = (start + end ) // 2

        # start1 为左区间的开始位置
        start1 = start

        # end1 为左区间的结束位置
        end1 = mid

        # start2 为右区间的开始位置
        start2 = mid + 1

        # end2 为右区间的结束位置
        end2 = end

        # 调用 merge_sort_recursive 函数,将 arr 数组中的 start1 到 end1 这一区间的数字排序后,并存放到 result 中
        self.merge_sort_recursive(arr, result, start1, end1)

        # 调用 merge_sort_recursive 函数,将 arr 数组中的 start2 到 end2 这一区间的数字排序后,并存放到 result 中
        self.merge_sort_recursive(arr, result, start2, end2)

        # 3、合并

        # 将左右区间中较小的数字存放到 result 中,从 k 开始
        k = start

        while start1 <= end1 and start2 <= end2 : 
            # 如果 arr[start1] < arr[start2])
            if arr[start1] <= arr[start2] : 
                # result[k] 存放的是 arr[start1]
                result[k] = arr[start1] 
                start1 += 1
                k += 1
            else : 
                # 否则,result[k] 存放的是 arr[start2]
                result[k] = arr[start2] 

                # 在这里统计逆序对
                self.count += (end1 - start1 + 1)

                start2 += 1

                k += 1

        # 如果左区间中还有元素,那么把它都添加到 result 中
        while start1 <= end1 : 
            result[k] = arr[start1]
            k += 1
            start1 += 1


        # 如果右区间中还有元素,那么把它都添加到 result 中
        while  start2 <= end2 : 
            result[k] = arr[start2]
            k += 1
            start2 += 1


        # 最后,把结果赋值到 arr 中
        for k in range( start , end + 1) :  
            arr[k] = result[k]
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。