1. 概要

このチュートリアルでは、配列内の反転をカウントする問題について説明します。 まず、問題を定義し、反転の意味を説明する例を示します。

次に、問題を解決するための2つのアプローチについて説明し、問題の適切な使用法について説明します。

2. 問題の定義

からに列挙される整数の配列があるとします。 要素の値はに等しくなります。

反転は、以下を満たすインデックスのペアです。

   

言い換えると、反転は2つの異なるインデックスのペアであり、これら2つのインデックスの順序はそれらの値の逆の順序になります。

問題は私たちに配列を与え、この配列の反転の数を計算するように求めます。

理解を深めるために例を確認してみましょう。

配列があるとします。 この場合の答えは、があり、反転しているためです。

配列がますますソートされる場合、反転の数はに等しいことに注意してください。 一方、配列が降順で並べ替えられる場合、反転の数は、配列のすべての順列で可能な最大数になります（要素がペアごとに異なる場合と同じになります）。

言い換えると、反転の数は、配列がソートされていない距離を示します。

3. 素朴なアプローチ

3.1. 本旨

アイデアは簡単です。 インデックスのすべてのペアを反復処理することでブルートフォースを実行し、このペアがセクション2で説明した条件を満たすかどうかを確認します。

3.2. 実装

実装を見てみましょう：

まず、ゼロで初期化します。これにより、結果の回答が保持されます。 次に、ペアの最初の要素を反復処理することから始めます。 次に、2番目の要素を繰り返し処理します。 から始めるので、それを保証することに注意してください。

次に、ペアをチェックして、反転条件を満たすかどうかを確認します。 はいの場合、新しい反転があり、反転の総数が1つ増えます。

最後に、結果のを返します。

素朴なアプローチの複雑さはです。ここで、はの長さです。

4. 分割統治アプローチ

4.1. 理論的アイデア

配列内の反転の数を数えたいとします。 それを2つの等しい配列に分割し、最初の配列と2番目の配列を呼び出しましょう。 これで、反転は次のいずれかのタイプになります。

  1. と 。
  2. と 。
  3. と 。

最初のタイプを考えてみましょう。 問題は、各インデックス、次のようなインデックスの数を計算することです。

ここで、両方の配列とがますますソートされると仮定すると、2ポインター手法を使用してそれを解決できます。これは、インデックスの条件を満たすインデックスが、大きくなると常に配列からプレフィックスを形成するためです。 、プレフィックスの長さが長くなります。

しかし、2番目と3番目のタイプはどうですか？ 答えは簡単です。同じアルゴリズムを両方に対して、そして独立して再帰的に実行するだけです。

最初のタイプに戻ると、両方とがますますソートされると想定しました。 これを実現するには、アルゴリズムでそれらを並べ替える必要があります。 つまり、との両方にアルゴリズムを適用した後、それらはソートされます。 並べ替えるには、並べ替えた2つの配列をマージして。

4.2. 実装

最初のタイプの反転の数をカウントする関数を実装することから始めましょう。

まず、ゼロで初期化します。これにより、結果の回答が保持されます。 次に、ゼロで初期化します。これは、現在の条件を破るの最初のインデックスです。 より正式には、それはそのような最初のインデックスです。 ゼロインデックス配列を使用しているため、は、条件を満たすプレフィックスの長さを表します。

増加する一方で、増加する必要があります。 これは、条件が再び解除されるまで続きます。

正しいを計算した後、それを未満の要素の数としてに追加します。

最後に、結果のを返します。

それでは、完全なアルゴリズムの実装を見てみましょう。

まず、配列の長さが。以下であるかどうかを確認します。 その場合、反転の数はに等しくなります。

それ以外の場合は、サブ配列を（包括的）から（排他的）に取得する関数を使用して、配列の前半と後半としてとを取得します。

次に、両方の半分で再帰的に呼び出すことにより、転倒の数を追加します。 両方ともソートされるので、関数を使用して最初のタイプの反転の数を計算できます。

その後、 2つの並べ替えられた配列を関数を使用して配列にマージし、それも並べ替えられるようにします。 両方の関数がコピーを取得するのではなく、配列への参照を取得すると想定します。 したがって、関数内で編集されると、編集は元の配列に影響します。

4.3. 複雑

前のアルゴリズムはマージソートアルゴリズムと非常に似ていることに注意してください。 唯一の違いは、最初のタイプの反転の数を数えるときに、配列の要素に対して別の反復を行うことです（最初の反復は、2つのサブ配列をマージしたときでした）。

したがって、複雑さはマージソートアルゴリズムと同じです。

5. 使用法

配列があり、配列をソートするための最小数の操作を見つけたいとします。 1つの操作で、隣接する2つの要素を交換できます。

答えは、反転の数です。 これは、各操作で、反転の数を。だけ減らすためです。 配列がソートされると、反転の数はに等しくなります。

6. 結論

このチュートリアルでは、配列内の反転の数をカウントする問題を示しました。 一般的な考え方を説明し、それを解決するための2つのアプローチについて説明しました。 また、議論された問題の公正な使用法を提供しました。