バイナリ配列が指定された場合、それをソートするために必要な隣接するスワップの最小数

ソートされた配列を取得するために隣接する要素間で必要なスワップの数を最小限に抑えるために使用できるさまざまな方法があります。指定された出力配列には 2 種類の要素 (0 と 1) のみが含まれています。この問題を解決する 2 つの異なる方法について説明します。1 つ目の解決策はゼロの数を格納するために追加のスペースを使用しますが、2 つ目の解決策は定数スペースのみを使用します。

＃＃＃問題文＃＃＃

0 と 1 の 2 つの要素のみを含む配列が与えられています。私たちの目標は、特定のバイナリ配列をソートするために必要なスワップの最小数を見つけることです。

Example

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

Example

リーリー

説明

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

説明

リーリー

ここで、この問題を解決する簡単な方法について説明します。

方法 1

このメソッドでは、0 と 1 の合計数を数えます。これは、各 1 の後に現れる 0 の数を数え、それらを合計することで実行できます。ご存知のとおり、並べ替えると、すべての 1 が配列の右端に配置され、すべての 0 が配列の左端に配置されます。これは、配列内のすべての 1 をその右側のすべての 0 と交換する必要があることを意味します。配列内の各要素に必要なスワップの数は、配列内の右側に表示される 0 の合計数になります。必要なスワップ数を取得するために、各 1 の左側に表示される 0 の合計数を加算し続けます。

Example

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

Example

以下の例では、7 つの数値のバイナリ配列を作成します。上記の方法を使用して、配列をソートするために必要な隣接スワップの最小数を見つけます。

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

上記の C プログラムを実行すると、次の出力が生成されます -

リーリー

このメソッドの時間計算量

- ループ内で n 回繰り返すため、時間計算量は次のようになります: O(n)

空間複雑度 - ゼロの数を格納するために追加の配列を使用するため、このメソッドの空間複雑度は O(n)

です。

次に、同じ問題に対するより適切で効率的な解決策を見てみましょう。私たちの新しいソリューションは追加のスペースを占有しないため、メモリを節約します。 方法 2

このアプローチでは、補助スペースを最小化して一定のスペースにします。配列を最初から読み取る代わりに、最後から繰り返して、見つかったすべてのゼロの数を数えます。 1 を取得した場合、その 1 をソートされた位置に配置するために必要なスワップの数は、その前に出現したゼロの数になります。

Example

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

Example

以下は、上記のメソッドの C 実装です -

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

上記の C プログラムを実行すると、次の出力が生成されます -

リーリー

このメソッドの時間計算量

- ループ内で n 回繰り返すため、時間計算量は次のようになります: O(n)

空間複雑度

- 余分な空間を使用していないため、空間複雑度は線形、つまり O(1) です。 この記事では、0 と 1 のみを含む配列をソートするために必要なスワップの最小数を計算する 2 つの方法について説明しました。最初のアプローチでは、各ステップの解を保存するために追加の配列を使用しましたが、2 番目のアプローチでは、一定の空間でそれを実行したため、空間の複雑さが改善されました。

以上がバイナリ配列が指定された場合、それをソートするために必要な隣接するスワップの最小数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。