1

アトレンタでのインタビューで面白い質問をされました。O（n）の複雑さの配列をソートすることでしたが、それは不可能だと私は言いましたが、インタビューの後でもそうだと彼は主張しました。

こんな感じです。

配列があります。たとえば、[1,0,1,0,1,1,0]とすると、これを並べ替える必要があります。配列内で実行する必要があること（他のデータ構造が関与しないという意味で）。

私はそうしていませんし、O（n）の複雑さでどんな種類のこともできるとは思いません。私が考えることができる最高のものはO（n * log n）であり、私の知識はウィキペディアから来ています。

あなたのアイデアとそれを行う方法を教えてください。

4

2 に答える 2

8

あなたの例では、配列には2つの異なる値しかないため、カウントソートを使用できます:

zero_count = 0
for value in array:
    if value == 0:
        zero_count += 1
for i in 0 ... zero_count:
    array[i] = 0
for i in zero_count ... array.size:
    array[i] = 1

基数ソートは、より一般的に適用可能な O(n) ソートのファミリーです。

平均して Omega(n * log n) 比較を必要とする比較ソートであるため、最悪の場合または平均的な場合の線形時間では実行できません。

于 2012-11-15T17:13:50.460 に答える
1

両端から配列をトラバースし、必要に応じて 1 と 0 を交換します。O(n) で実行されますが、すべての if 条件があります (アプローチのようなブルー​​トフォース。おそらく期待される答えではありません) ;)

int i = 0 ;
int j = array.size -1 ;
for ( i = 0 ; i < j ; ) {

    if( array[i] == 1) {
        if( array[j] == 0 ) {
            array[j] = 1 ; array[i] = 0 ; //Swap 
            i++; j--; 
            continue;
        }
        //else
            j--;
            continue;

    }
   //else
        if( array[j] == 0 ) {
            i++; 
            continue;
        }

        //else 
            i++ ;
            j--;            
}
于 2012-12-05T06:29:17.333 に答える