7

0s n 1sのみで構成される配列をソートするには、高度に最適化されたアルゴリズムを見つける必要があります。

解決策の私のバージョンは、番号を数えることです。ゼロ（たとえばx）と1（たとえばy）の。これを行ったら、配列にx個のゼロを配置し、その後にy1を配置します。これにより、O（n）になります。

これよりもうまくいくアルゴ??? 私はインタビューでこの質問をされました。

4

6 に答える 6

10

各入力要素を調べる必要があるためn、を改善することはできませんO(n)。

また、アルゴリズムにはO(1)メモリが必要なため、それを改善することもできません（漸近的に優れているものはありませんO(1)）。

于 2012-05-17T14:44:33.523 に答える
7

O（n）よりもうまくいくことはできませんが、1回のパスでできるように見えます

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）時間アルゴリズムが開発されています。「高速ビットカウントルーチン」を参照してください。

これはそこで提示されているアルゴリズムの1つです。彼らがNiftyParallelCountと呼んでいるもの：

#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 に答える