2

我需要编写一个对大小为 [0..N-1] 的数组进行排序的算法，该算法填充了范围 [0..N-1] 的值。数组中的值不能重复。排序应该在线性时间内工作，我只允许使用一些额外的变量。

请评论我写的代码。据我猜测，最糟糕的时间是 2*N。难道还是线性时间？是否有可能更快？

public int sort(){
    int i  = 0;             
    while (i < n){
        if (a[i] != i)      
            switchElements(a[i], a[a[i]]);                  
        else
            i++;                    
    }
    return count;
}

附加 1 我真的需要对数组进行排序，因为排序只是任务的一部分。完整的任务是在线性时间内查找数组中是否存在重复值，并且没有其他变量。

4

2 回答 2

5

回答原始问题：

带有元素的数组[0..N-1]，包含不重复的元素[0..N-1]

为什么还要排序？排序后的数组是已知的并且是[0..N-1].

考虑到您的附加 1：您的算法看起来不错，您正在查看每个元素一次，并且必须至少查看每个元素一次，因此它不会变得更好。亦2*N是也O(N)。

于 2012-11-12T19:10:37.860 回答
1

为了检测重复项，您可以进一步扩展该逻辑，将值强制放入各自的位置。

public int sort(){
    int i  = 0;             
    while (i < n){
        while (a[i] != a[a[i]])      
            switchElements(a[i], a[a[i]]);                  
        ++i;                    
    }
    return count;
}

最后，如果对于任何i, i并且A[i]不匹配，则表示重复！
总的来说，它仍然是O(N)程序。

有关更多详细信息，请参阅以下帖子：
在 O(n) 时间和 O(1) 空间中查找重复项

于 2012-11-12T19:39:44.590 回答