7

我需要找到一个高度优化的算法来对仅由 0s n 1s 组成的数组进行排序。

我的解决方案是数数。零（比如 x）和一（比如 y）。一旦你这样做了，在数组中放置 x 个零，然后是 y 1s。这使它成为 O(n)。

任何比这运行得更好的算法？？？我在面试中被问到这个问题。

4

6 回答 6

10

由于您必须检查每个n输入元素，因此您无法改进O(n).

此外，由于您的算法需要O(1)内存，因此您也无法对此进行改进（没有什么比 渐近更好了O(1)）。

于 2012-05-17T14:44:33.523 回答
7

我们不能比 O(n) 做得更好，但看起来我们可以一次性完成

low = 0; 
high = arr.length - 1;

while (low < high) {
    while (arr[low] == 0) {
        low ++;
    }
    while (arr[high] == 1) {
        high --;
    }
    if (low < high) {
    //swap arr[low], arr[high]
    }
}
于 2012-05-17T22:50:02.263 回答
5

如果对数组求和，则可以得到 1 的数量，效率稍高，但仍为 O(n)。

于 2012-05-17T14:39:52.253 回答
3

你不能比 O(N) 更有效率，因为每个项目都需要检查。

于 2012-05-17T14:39:59.123 回答
2

我们在谈论什么样的“阵列”？如果我们要对 16 位无符号整数中的位进行计数，那么已经开发了几种 O(1) 时间算法：请参阅快速位计数例程。

这是那里提出的算法之一；他们称之为 Nifty Parallel Count：

#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)
int bitcount (unsigned int n) {
   n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101);
   n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011);
   n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111);
   return n % 255 ;
}
于 2012-05-17T14:50:22.317 回答
0

这听起来像是单杆算盘排序。现在我很好奇你的面试官是谁。

http://www.dangermouse.net/esoteric/abacussort.html

于 2012-05-21T22:06:28.203 回答