2 種類の要素を含む配列をソートする

2 種類の要素 (つまり、1 と 0 のみ) のみを含む配列を並べ替えるには、さまざまな方法があります。この目標を達成するための 3 つの方法について説明します。最初の方法は、単純に定義済みの sort() 関数を使用して、指定された配列を並べ替えます。 2 番目の方法は、0 と 1 の数を数えてから、最初に 0 の数を書き込み、次に 1 の数を書き込むことによって配列を更新するカウント ソート メソッドです。最後の方法では、ダブル ポインター方法を使用しました。

＃＃＃問題文＃＃＃

1 と 0 だけを含む配列が与えられました。私たちのタスクは、1 が配列の右端に、0 が配列の左端になるように、すべての 0 と 1 を配置することです。

Example

の中国語訳は次のとおりです:

Example

リーリー

方法 1: ブルート フォース クラッキング方法。

このメソッドでは、sort() 関数を使用して配列を直接並べ替えます。 1>0 なので、並べ替えると、配列の右側にはすべて 1 が配置され、左側にはすべての 0 が配置されます。

Sort() 関数: Sort() 関数は O(NlogN) 時間かかり、配列を昇順で返します。

Example

の中国語訳は次のとおりです:

Example

以下は、2 種類の要素を含む配列をソートするための C 実装です。

リーリー ＃＃＃出力＃＃＃

上記のプログラムをコンパイルすると、次の出力が生成されます -

リーリー

方法 2: カウントソート方法

このメソッドでは、配列内の 0 と 1 の数を単純に数え、先頭が 0、末尾が 1 で配列を更新します。

これを行うと、配列の左端の部分がすべて 0 になり、配列の右端の部分がすべて 1 になり、目的の並べ替えられた配列が自動的に表されます。

これは単純な方法ですが、単に位置を交換するのではなく、新しい値を配列に挿入するため、この方法は効率的ではありません。

Example

の中国語訳は次のとおりです:

Example

以下は、C を使用した上記のメソッドの実装です。

リーリー ＃＃＃出力＃＃＃

コンパイルすると、次の出力が生成されます -

リーリー

時間計算量

- ループを 1 つだけ使用するため、このメソッドの時間計算量は O(N)

です。

空間複雑度

- O(1)。追加の変数を使用しますが、それらは線形であるため、空間の複雑さは一定です。

方法 3: この問題を解決する最良の方法

このメソッドでは、開始と終了の 2 つのポインターを保持します。開始ポインターを使用して配列の先頭 (インデックス 0) からトラバースし、終了ポインターを使用して末尾 (インデックス len-1) からトラバースすることを同時に行います。

私たちのタスクは、すべての 1 を配列の右端に配置することです。これにより、すべての 0 が自動的に配列の左側に配置されます。

最初のインデックスから開始します。見つかった要素が 1 の場合、それをインデックス「end」の要素と交換し、終了ポインタを 1 だけデクリメントします。

見つかった要素が 0 の場合、要素はすでに左端の位置にあるため、交換操作を実行する必要はありません。開始ポインターを 1 増やすだけで済みます。

Example

の中国語訳は次のとおりです:

Example

以下は、このメソッドを実装するコードです -

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量

- 配列を 1 回だけ反復するため、このメソッドの時間計算量は線形です、つまり O(N)

空間複雑度

-余分な空間を使用していないため、空間複雑度はO(1)です。

＃＃＃結論は＃＃＃

この記事では、2 種類の要素 (つまり、1 と 0 のみ) のみを含む配列を並べ替える 3 つの異なる方法について説明しました。

以上が2 種類の要素を含む配列をソートするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。