题目描述

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

输入一个数组，求出这个数组中的逆序对的总数。

样例

输入：[1,2,3,4,5,6,0]

输出：6

算法

(归并排序) $O(nlogn)$

归并排序的过程中计算逆序对的数量，更精细的来说是在合并两个有序序列时计算逆序对的数量，对于两个有序序列，如 $\{4, 5\}$ 和 $\{1, 2\}$，i 和 j 指向序列的第一个元素 $i = 0, j = 3, mid = 1$，对于 $1$ 可以构成两个逆序对 $<4, 1>$ 和 $<5, 1>$ 即 mid - i + 1 = 2，同样对于 2 也有两个逆序对 $<4, 2>$ 和 $<5, 2>$，即 mid - i + 1 = 2

$mid - i + 1$ 表示的是区间 $[i, mid]$ 的长度，依然拿上面的例子看，对于 $4$ 来说，$4$ 可以和 $1$ 构成逆序对，由于是有序序列，那么 $4$ 之后的数同样也可以和 $1$ 构成逆序对，即区间 $[i, mid]$ 的元素个数就是和 $j$ 可以构成的逆序对个数$。

所以当 $nums[i] > nums[j]$ 时更新逆序对的数量即可

时间复杂度

归并排序的时间复杂度为 $O(nlogn)$

C++ 代码

class Solution {
public:
    int merge(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;

        int mid = l + r >> 1;
        int res = merge(nums, l, mid) + merge(nums, mid + 1, r);

        vector<int> temp;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j]) temp.push_back(nums[i ++ ]);
            else 
            {
                temp.push_back(nums[j ++ ]);
                // 计算逆序对的数量
                res += mid - i + 1;
            }
        }

        while (i <= mid) temp.push_back(nums[i ++ ]);
        while (j <= r) temp.push_back(nums[j ++ ]);


        i = l;
        for (auto x : temp) nums[i ++ ] = x;

        return res;
    }

    int inversePairs(vector<int>& nums) {
        return merge(nums, 0, nums.size() - 1);
    }
};