计算排列中的"反转"数

Question

设A是一个大小的数组N.(i,j)如果i < j和,我们将几个索引称为"反向"A[i] > A[j]

我需要找到一个接收大小数组N(带有唯一数字)的算法,并返回时间的倒数O(n*log(n)).

Answer 1

您可以使用合并排序算法.

在合并算法的循环中,左半部分和右半部分都是按升序排序的,我们希望将它们合并为单个排序的数组.请注意,右侧的所有元素都具有比左侧更高的索引.

假设array [leftIndex]> array [rightIndex].这意味着左侧部分中索引为leftIndex的元素后面的所有元素也大于右侧的当前元素(因为左侧是按升序排序的).因此右侧的当前元素生成numberOfElementsInTheLeftSide - leftIndex + 1反转,因此将其添加到全局反转计数中.

一旦算法完成执行,你得到你的答案,并且在最坏的情况下合并排序是O(n log n).

Answer 2

Cham和Patrascu于2010年在SIAM上发表了一篇题为计数反演,离线正交范围计数和相关问题的文章,该文章给出了一个采用O(n sqrt(log(n)))时间的算法.这是目前最着名的算法,并且改进了长期存在的O(n log(n)/ log(log(n)))算法.从摘要:

我们给出一个O(n sqrt(lg n))时间算法,用于计算n个元素上的置换中的反转次数.这改善了从Dietz的数据结构[WADS'89]开始的O(n lg n/lg lg n)的长期先前界限,并回答了Andersson和Petersson [SODA'95]的问题.由于Dietz的结果已知是相关动态排名问题的最佳结果,因此我们的结果显示了离线设置的显着改进.

我们的新技术非常简单:我们执行trie的"垂直分区"(类似于van Emde Boas树),并使用来自外部存储器的想法.然而,该技术发现了许多应用:例如,我们获得

• 在d维中,用于在时间O(n lg ^{d-2 + 1/d} n)内回答n个离线正交范围计数查询的算法;
• 改进正交范围计数在线数据结构的建设时间;
• 改进了部分和问题的更新时间;
• 更快的Word RAM算法,用于在轴对齐矩形的排列中找到最大深度,以及用于斜率选择问题.

作为奖励,我们还提供了一种简单的(1 +ε)近似算法,用于计算在线性时间内运行的反演,从而改善了Andersson和Petersson约束的先前 O(n lg lg n).

Answer 3

我认为最好的方法(这只是因为我喜欢数据结构)是使用二进制索引树.请注意,如果你需要的只是一个解决方案,合并排序也会起作用(我只是认为这个概念完全是摇滚!).基本思想是这样的:构建一个更新O(log n)中的值的数据结构,并回答查询"到目前为止,数组中已经发生了多少小于x的数字？" 鉴于此,您可以轻松回答有多少大于x,这有助于反转,x作为对中的第二个数字.例如,考虑列表{3,4,1,2}.

当处理3时,到目前为止没有其他数字,因此右侧3的反转= 0当处理4时,到目前为止小于4的数字= 1,因此数字越多(因此反转)= 0现在当处理1时,数字的数量小于1 = 0,这个数字越大= 2,这有助于两个反转(3,1)和(4,1).同样的逻辑适用于2,它找到比它小1的数字,因此比它大2.

现在,唯一的问题是要了解这些更新和查询如何在log n中发生.上面提到的url是我读过的关于这个主题的最好的教程之一.