题目

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

• 0 <= 数组长度 <= 50000

示例

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

分析

• 逆序对反映了一个数组的有序程度。

思路 1：暴力解法

• 遍历求出每个数字后面比他小的数字个数和
• 时间复杂度 O(n^2)
• 空间复杂度 O(1)
• 结果：计算结果超时

思路 2：归并排序