2 種類の要素 (つまり、1 と 0 のみ) のみを含む配列を並べ替えるには、さまざまな方法があります。この目標を達成するための 3 つの方法について説明します。最初の方法は、単純に定義済みの sort() 関数を使用して、指定された配列を並べ替えます。 2 番目の方法は、0 と 1 の数を数えてから、最初に 0 の数を書き込み、次に 1 の数を書き込むことによって配列を更新するカウント ソート メソッドです。最後の方法では、ダブル ポインター方法を使用しました。
###問題文###の中国語訳は次のとおりです:
ExampleExample
の中国語訳は次のとおりです:
Exampleリーリー
方法 2: カウントソート方法これを行うと、配列の左端の部分がすべて 0 になり、配列の右端の部分がすべて 1 になり、目的の並べ替えられた配列が自動的に表されます。
Example
の中国語訳は次のとおりです:
Example以下は、C を使用した上記のメソッドの実装です。
時間計算量
- ループを 1 つだけ使用するため、このメソッドの時間計算量は O(N)空間複雑度
- O(1)。追加の変数を使用しますが、それらは線形であるため、空間の複雑さは一定です。方法 3: この問題を解決する最良の方法
このメソッドでは、開始と終了の 2 つのポインターを保持します。開始ポインターを使用して配列の先頭 (インデックス 0) からトラバースし、終了ポインターを使用して末尾 (インデックス len-1) からトラバースすることを同時に行います。私たちのタスクは、すべての 1 を配列の右端に配置することです。これにより、すべての 0 が自動的に配列の左側に配置されます。
最初のインデックスから開始します。見つかった要素が 1 の場合、それをインデックス「end」の要素と交換し、終了ポインタを 1 だけデクリメントします。Example
の中国語訳は次のとおりです:
Example以下は、このメソッドを実装するコードです -
リーリー ###出力### リーリー
空間複雑度
-余分な空間を使用していないため、空間複雑度はO(1)です。以上が2 種類の要素を含む配列をソートするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。