我想知道我们到底是如何计算两个数组之间的倒数的。
例如，假设我们有以下两个数组：
A=[1，2，3，4，5，6]
B=[6，3，5，4，2，1]
我如何从概念上计算倒数也就是说，只看这两个数组，而不考虑所涉及的编码。
另外，我知道在两个数组之间绘制线段的约定，但我试图在这里获得更深入的理解。
谢谢您！
最佳答案
我不知道你说的两个数组的倒数是什么意思。
对于一个数组：
反转是一对（a，b），其中a在b之前，但a>b。
所以，从概念上讲，你可以试着用每一对b。让我们从6开始，有5个倒数：（6,3），（6,5），（6,4），（6,2），（6,1）。接下来是3，只有2:（3,2），（3,1）等等，结果是13。
然而，这个算法相当幼稚，运行o（n^2）。更好的解决方案是基于合并排序算法，它在o（n logn）中运行。你可以检查它here我认为这只适用于第一个已经排序的数组。
对于两个数组：当涉及到两个数组（同样是概念上的）时，只需在数组上方键入b数组并绘制连接相同元素的线。交叉口的数量应该是倒转的数量。这正是上面链接的基于合并排序的算法的工作原理请看下面的图片：
结果仍然是13，所以这个方法确实有效。
关于algorithm - 计算反转次数(从概念上讲？)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11822589/