剑指 Offer 51. 数组中的逆序对

题目

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

思路

K神的题解：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/

代码

class Solution {
    
public:
    int reversePairs(vector<int>& nums) {
    
        vector<int>  tmp(nums.size());
        return mergeSort(0,nums.size() - 1,nums,tmp);
    }

private:
    int mergeSort(int l,int r, vector<int>& nums, vector<int>& tmp)
    {
    
        // 终止条件
        if(l >= r) return 0;

        // 递归划分
        int m = (l + r) / 2;
        int res = 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++)
        {
    
            // m及左边元素合并完成 把右边剩下的放入合并之后的数组
            if(i == m + 1)
            {
    
                nums[k] = tmp[j ++];
            }
            else if(j == r + 1 || tmp[i] <= tmp[j])
            {
    
                // m + 1及右边的元素合并完成 将左边剩下的元素放入合并之后的数组
                // 或者左边数组的元素小于等于右边，将左边数组的元素放入结果数组中，并让索引i加1
                nums[k] = tmp[i ++];
            }
            else
            {
    
                // 右边数组的元素小于左边，将右边数组的元素放入结果数组中，并让索引+1
                // 并且此时左边数组中的从i到m所有数都是大于tmp[j]的（因为左边的数组已经排序完毕）
                nums[k] = tmp[j++];
                res += m - i + 1;// 统计逆序对
            }
        }

        return res;
    }

};