剑指 Offer 51. 数组中的逆序对（困难）

孜孜不倦fly / 2023-08-23 / 原文

题目：

class Solution {      //这道题利用了归并排序（分而治之）的思想，就是在每一次排序中统计逆序对的个数
public:
    int mergesort(int l, int r, vector<int>& nums, vector<int>& tmp) {      //tmp用于记录合并之前的两个子数组
        if(l>=r) return 0;
        //递归划分子数组
        int m=(l+r)/2;
        int result=mergesort(l, m, nums, tmp)+mergesort(m+1, r, nums, tmp);    
        //递归排序合并，并且计算逆序对
        int i=l, j=m+1;
        for(int k=l;k<=r;k++){
            tmp[k]=nums[k];
        }
        for(int k=l;k<=r;k++){      //循环遍历直到合并成l-r+1个数的数组。小的数先放入num中
            if(i==m+1){      //左子数组合并完，只需要添加当前右子数组
                nums[k]=tmp[j++];
            }
            else if(j==r+1||tmp[i]<=tmp[j]){      //右子数组合并完或左子数组当前元素小于当前右子数组元素，添加当前左子数组元素
                nums[k]=tmp[i++];
            }
            else{      //左子数组当前元素大于当前右子数组元素，当前左子数组剩下元素也都大于当前右子数组元素，添加添加当前右子数组，且逆序对个数为m-i+1
                nums[k]=tmp[j++];
                result+=m-i+1;
            }
        }
        return result;
    }

    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return mergesort(0, nums.size()-1, nums, tmp);
    }
};

作者：Krahets
链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/622496/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
来源：力扣（LeetCode）