这是一个电话采访问题：“查找数组中的反转次数”。我猜他们的意思是O（N log N）解决方案。 我相信它不能比O（N log N） 更好， 因为这是排序的复杂性。
对类似问题的答案可总结如下：
计算元素移动以对数组进行排序的距离的一半：复制数组并对副本进行排序。对于原始数组的每个元素，在排序后的副本中a[i]找到它的位置j（二进制搜索），并将距离相加一半abs(i - j)/2。
a[i]
j
abs(i - j)/2
修改merge sort：修改merge以计算两个排序数组之间的求反，并在merge sort修改后正常运行merge。
merge sort
merge
是否有意义 ？还有其他（也许更简单）的解决方案吗？电话采访不是很辛苦吗？
它实际上是分治法的应用程序，如果您熟悉它，则可以快速提出解决方案。
以[1 3 8 5 7 2 4 6]为例，假设我们将数组排序为[1 3 5 8]和[2 4 6 7]，现在我们需要组合两个数组并获得总数倒置。
由于每个子数组中已经存在反转次数，因此我们只需要找出由数组合并引起的反转次数。每次插入一个元素，例如，将2个元素插入[1＃3 5 8]中，您就可以知道第一个数组与元素2之间有多少个反转（在此示例中为3对）。然后，您可以将它们相加以获得合并引起的反转次数。
