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

示例 1:

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

输出: 5

来源：力扣（LeetCode）

链接：

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

如果使用暴力解法，时间复杂度是o(n2)。有没有时间复杂度更低的算法呢。有，归并排序很适合解决这类逆数对问题。

设原数组区间为[l, r]，令m=(l+r)/2，则区间被分为[l, m]，[m+1, r]。

设versed[l, r]表示区间[l, r]逆数对个数。

则versed[l, r]=versed[l, m] + versed[m+1, r] + [l, m]和[m+1, r]之间的逆数对个数。

如果归并排序[l, m]和[m+1, r]过程中已经计算出了versed[l, m] + versed[m+1, r] ，那么只需要在合并[l, m]，[m+1, r]过程中，计算[l, m]和[m+1, r]之间的逆数对个数即可。

如果计算呢，举例说明如下。

[l, m]：2 6 9 11

[m+1, r]：4 8 9 10

显然，我们现在需要求的是[l, m]和[m+1, r]之间的逆数对个数，就是[l, m]中每个元素在[m+1, r]中可能的逆数对个数。

设指针lptr指向2，rptr指向1。

第一次比较：

2<4，2被放入合并的临时数组tmp中。此时rptr偏移量是0，说明2的逆序对个数是0。

第二次比较：

lptr++，指向6，6>4，此时4加入tmp中。

第三次比较：

rptr++，指向8，6<8，此时6加入tmp中，rptr偏移量是1，说明存在1个逆序对。

很显然，是[6, 4]。

...

在[l, m]中的元素需要加入tmp时，就可以根据此时rptr的偏移量来确定逆序数。这就是在合并过程中实现的，体现了归并排序的高效性，本质上是省去了[l, m]，[m+1, r]各自区间逆序对的重复计算，只需要计算两者之间的逆序对。

你还可以挑战下：《计算右侧小于当前元素的个数 315》

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例：

输入：nums = [5,2,6,1]

输出：[2,1,1,0]

解释：

5 的右侧有 2 个更小的元素 (2 和 1)

2 的右侧仅有 1 个更小的元素 (1)

6 的右侧有 1 个更小的元素 (1)

1 的右侧有 0 个更小的元素

来源：力扣（LeetCode）

链接：

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题是求右边小于当前元素的个数，和16.2.1本质上是一个问题，逆数对问题。只是这道题是求每个元素自己的逆数对，不是全部的逆数对，应该怎么解决呢。

只需要弄清楚一个细节问题：

如果计算呢，举例说明如下。

[l, r]：7 3 2 6 8 4 9 10

由于归并排序是从最小的组开始合并，按令m=(l+r)/2来分组，过程如下

[7 3 2 6] [8 4 9 10]

[7 3] [2 6] [8 4] [9 10]

[7] [3] [2] [6] [8] [4] [7] [10]

我们拿7来说明问题，先合并最小层，只考虑有7那组，即

[l, m]：[7]

[m+1, r]：[3]

经过合并操作会变成[3] [7]，7>3，这个过程会统计处理到7的逆数对有一对，versed[7] +=1，versed[7] =1。具体统计过程参考16.2.1

最小层合并后，变为：

[3 7] [2 6] [4 8] [9 10]

然后合并倒数第二层[3 7] [2 6] [4 8] [9 10]，只看有7的部分，即

[l, m]：[3 7]

[m+1, r]：[2 6]

7>2，7>6，合并过程统计到7的逆数对有2对，versed[7] +=2，versed[7]=3。

合并后变成：

[2 3 6 7] [4 8 9 10]

然后合并倒数第三层[2 3 6 7] [4 8 9 10]，也是最后一次合并操作，即

[l, m]：[2 3 6 7]

[m+1, r]：[4 8 9 10]

7>4，合并过程统计到7的逆数对有一对，versed[7] +=1，versed[7]=4。

合并后变成：

[2 3 4 6 7 8 9 10]

综上排序完成，逆数对也统计完成，7的逆数对有4对，分别为[7, 3]，[7, 2]，[7, 6]，[7, 4]。

上面的操作过程主要是演示归并过程是如何能统计到某个数字全部的逆数对的。

还有个问题是，统计完后，数字已经被排好序了，比如计算出了versed[7]=4，由于7是第0个元素，返回的答案要写ans[0] = 4。这个对应关系怎么确定呢。有两种方法。

方法1：创建一个结构体，包含了索引和索引对应的数据，根据数据，可以获取索引。

Struct dataS

{

index，

data

}

方法2：不需要创建结构体，只需要在排序时，合并的内容变为索引，而不是数据本身即可。

比如[7 3] -> [3 7]过程，我们使用索引代替[0 1] -> [1 0]，当然合并时，比较元素大小还是需要根据索引对应的数据来判断的。