是否有算法在线性时间内计算数组反转？

我知道使用增强的合并排序可以在O（ n log（ n ））操作中计算n元素数组中的反转次数。

但是，我遇到了一个不同的解决方案，它以某种方式设法计算O（ n ）时间内的反转次数，前提是输入是（1,2,3，…， n -1， n ）的置换：

编辑：-

---

我很抱歉我粘贴的代码因为它在所有情况下都不起作用。 实际上这个代码用于这个问题 ，它通过了所有的情况。 但我仍然离开代码，以便它可以作为一些直觉，也许这个问题的线性时间解决方案将会出现。

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

---

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

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

Answer 1

显而易见的答案是它没有。 例如，对于n = 4和a = {2, 3, 4, 1} ，您的代码给出答案5，即使正确的反转计数明显为3。

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！