有没有一种算法来计算阵列倒线性时间？ [英] Is there an algorithm to count array inversions in linear time?

问题描述

我知道，反转的数量在 N k-元阵列可以在O计数（ N 的日志（ N 的））使用的增强归并排序。

I know that the number of inversions in an n-element array can be counted in O(n log(n)) operations using an enhanced merge sort.

不过，我遇到了一个不同的解决方案，它以某种方式管理数为O反转的数目（ N 的）时，只要输入的置换（1，2，3， ...，的 N 的和减1， N 的）：

However, I came across a different solution, which somehow manages to count the number of inversions in O(n) time, provided that the input is a permutation of (1, 2, 3, ..., n−1, n):

编辑： -

我很抱歉code我粘贴，因为它没有在所有的情况下工作。其实这code用于这个问题，并通过了所有的情况。但我还是离开code，以便它可以作为一些直觉，也许对于这个问题的一个线性时间的解决方案上来了。

I am sorry for the code I pasted as it doesn't work in all the cases . Actually this code was used for this question and it passed all the cases . But I am still leaving the code so that it may serve as some intuition and maybe a linear time solution for this problem will come up.

/* 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;
    } */ 

现在的问题是，我们才能想出了这个问题的线性时间的解决方案？

Now the question is can we come up with a linear time solution for this problem ?

推荐答案

显而易见的答案是，事实并非如此。例如， N = 4 和 A = {2，3，4，1} ，你code给出的答案5，即使正确反转计数显然3

The obvious answer is that it doesn't. For example, for n = 4 and a = {2, 3, 4, 1}, you code gives the answer 5, even though the correct inversion count is clearly 3.

这篇关于有没有一种算法来计算阵列倒线性时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！