有没有一种算法可以在线性时间内计算数组逆序对？

Question

我知道使用改进的归并排序，可以在O(n log(n))的时间内计算出n元素数组中逆序对的数量。然而，我发现了一种不同的解决方案，只要输入是(1, 2, 3, ..., n−1, n)的排列，就可以在O(n)的时间内计算逆序对的数量。注意：编辑后的内容如下：

---

很抱歉我贴上的代码并不适用于所有情况。实际上，这段代码是用于this question的，并且它通过了所有测试用例。但我仍然保留这段代码，以便它可能作为一些直觉和可能的线性时间解决方案来使用。

注意：下面提到的代码是不正确的。

---

/* int in = 0;
    for (int i = 0; i < n; i++) {
        a[i] = a[i] - i - 1;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] > 0)
            in = in + a[i];
        else if (a[i] < -1)
            in = in - a[i] - 1;
    } */ 

现在的问题是，我们能否为这个问题提出一个线性时间的解决方案？

- Raman Singh

---

这段代码复制正确吗？i 在内部和外部的 for 循环中都被修改了吗？ - Mike

在这种情况下，“inversion”究竟是什么意思？ - bytefire

@Mike，是的，我已经修改了。看起来是stackoverflow编辑错了。 - Raman Singh

@Spundum 这是使用归并排序计算逆序对的链接 http://www.geeksforgeeks.org/counting-inversions/。 - Raman Singh

@Spundum 归并排序方法是一种通用算法，适用于任何类型的数组，但上述算法仅适用于数组是1、2、3...N的随机排列时。例如，如果N=4，则数组可以是2、4、3、1。 - Raman Singh

Answer 1

明显的答案是它不能。例如，对于 n = 4 和 a = {2, 3, 4, 1}，你的代码给出的答案是5，即使正确的逆序计数显然是3。

- Ilmari Karonen

Answer 2

方法是错误的！考虑下面的例子！

int a[] = { 2, 3, 1 };

int in = 0;

for (int i = 0; i < n; i++) {
    a[i] = a[i] - i - 1;
}

// a[] = { 1, 1, -2 };

for (int i = 0; i < n; i++) {
    if (a[i] > 0)
        in = in + a[i];
    else if (a[i] < -1)
        in = in - a[i] - 1;
} 

// in = 1 + 1 - (-1) = 3

正确答案是2，但这里返回了3！

- Alfred Huang