如何查找数组中的倒数个数？

Question

可能重复：

Counting inversions in an array

这是一个phone interview question：“查找数组中的倒数”。我猜他们的意思是O(N_log N)解。我相信它不会比O(N_log N)更好，因为这是排序的复杂性。

similar question的答案可以总结如下：

1. 计算元素移动距离的一半来对数组进行排序:复制数组并对副本进行排序。对于原始数组a[i]的每个元素，找到它在排序副本中的位置j (二进制搜索)，并将距离abs(i - j)/2.

的两部分相加

1. Modify merge sort：修改merge以计算两个排序数组之间的倒数，并使用修改后的merge运行常规merge sort。

这有意义吗？还有其他(也许更简单)的解决方案吗？电话面试是不是太难了？--

Answer 1

它实际上是分而治之算法的一个应用，如果你熟悉它，你可以很快找到解决方案。

以1 3 8 5 7 2 4 6为例，假设我们已经将数组排序为1 3 5 8和2 4 6 7，现在我们需要将这两个数组组合起来，得到总的倒数。

因为我们已经在每个子数组中有了倒数，所以我们只需要找出由数组合并引起的倒数。每次插入一个元素，例如，2插入到1#3 5 8中，您就可以知道第一个数组和元素2(在本例中为3对)之间有多少个反转。然后，您可以将它们相加，以获得合并导致的反转次数。

Answer 2

您还可以使用类似计数排序的方法，例如，如果数组只包含较小的数字(例如，如果它是一个字符数组)：

inversions = 0
let count = array of size array.Length
for i = 0 to array.Length - 1 do
    for j = array[i] + 1 to maxArrayValue do
        inversions = inversions + count[j]

    count[array[i]] = count[array[i]] + 1

基本上，对每个元素出现的次数进行计数。然后，在每一步i中，ith元素生成的倒数等于i之前大于i的所有元素的总和，您可以使用所保留的计数轻松地计算出该值。

这将是O(n*eps)，其中eps是数组中元素的域。

在我看来，这绝对更简单。至于效率，只有在eps很小的情况下才是好的。如果是，那么它应该比其他方法更快，因为没有递归。