计算排列中“逆序对”的数量

Question

假设A是大小为N的数组。 如果i<j且A[i] > A[j]，则我们称索引对(i,j)为“逆序”。

我需要找到一个算法，在O(n*log(n))的时间内接收大小为N（具有唯一数字）的数组，并返回其逆序数。

- Shai Balassiano

---

非常相似：https://dev59.com/zm455IYBdhLWcg3wFP9u。不同之处在于，这个指定数组包含一个排列，而不是任意值。 - Steve Jessop

还相关的：在数组中计算逆序对 - PengOne

Answer 1

你可以使用归并排序算法。

在归并算法的循环中，左半部分和右半部分都按升序排列，我们想将它们合并成一个已排序的数组。请注意，右侧所有元素的索引都比左侧的高。

假设array[leftIndex] > array[rightIndex]。这意味着在具有索引leftIndex的元素之后的左侧部分中的所有元素也大于右侧当前元素（因为左侧按升序排列）。因此，右侧当前元素会生成numberOfElementsInTheLeftSide - leftIndex + 1个逆序对，因此将其添加到您的全局逆序计数中。

一旦算法执行完成，您就得到了答案，而归并排序在最坏情况下是O(n log n)。

- IVlad

Answer 2

2010年，Cham和Patrascu在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)界限有所改进。

- PengOne

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，因此有2个比它大的数字。

现在，唯一的问题是要理解这些更新和查询如何在log n中发生。上面提到的URL是我读过最好的教程之一。

- kyun

Answer 4

这是Cormen、Leiserson、Rivest和Stein的《算法导论》中关于MERGE和MERGE-SORT算法的原始内容：

MERGE(A,p,q,r)
 1  n1 = q - p + 1
 2  n2 = r - q
 3  let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
 4  for i = 1 to n1
 5      L[i] = A[p + i - 1]
 6  for j = 1 to n2
 7      R[j] = A[q + j]
 8  L[n1 + 1] = infinity
 9  R[n2 + 1] = infinity
10  i = 1
11  j = 1
12  for k = p to r
13      if L[i] <= R[j] 
14          A[k] = L[i]
15          i = i + 1
16      else A[k] = R[j]
17          j = j + 1

并且

MERGE-SORT(A,p,r)
 1 if p < r
 2     q = floor((p + r)/2)
 3     MERGE-SORT(A,p,q)
 4     MERGE-SORT(A,q + 1,r)
 5     MERGE(A,p,q,r)

在MERGE无限循环的第8和9行，有所谓的哨兵卡片，其值比所有数组元素都小。 为了获得逆序对的数量，可以引入一个全局计数器ninv，在调用MERGE-SORT之前初始化为零， 然后通过在else语句中添加一行代码来修改MERGE算法，例如在第16行后添加：

ninv += n1 - i

当MERGE-SORT完成后，ninv将保存逆序对的数量。

- baz