algorithm - 配列内の要素間の最小差を見つける

Question

有限数の値を持つ整数配列があります。私の仕事は、配列内の任意の 2 つの要素間の最小の差を見つけることです。

配列が含まれていると考えてください

4, 9, 1, 32, 13

ここでは、差は 4 と 1 の間で最小であるため、答えは 3 です。

この問題にアプローチするアルゴリズムはどうあるべきか. また、理由はわかりませんが、ツリーを使用すると、この問題は比較的簡単に解決できると思います。それはできますか？

Answer 1

最小差は、ソートされた順序で連続するペアの中からの差の 1 つになります。配列を並べ替え、隣接する数値のペアを調べて最小の差を探します。

int[] a = new int[] {4, 9, 1, 32, 13};
Arrays.sort(a);
int minDiff = a[1]-a[0];
for (int i = 2 ; i != a.length ; i++) {
    minDiff = Math.min(minDiff, a[i]-a[i-1]);
}
System.out.println(minDiff);

これは印刷され3ます。

Answer 2

線形アルゴリズムを作成するために整数を検討しているという事実を利用できます。

1. 最初のパス: 最大値と最小値を計算します
2. 2 番目のパス: 長さ (最大 - 最小 + 1) のブール配列を割り当て、false を初期化し、配列内のすべての値に対して (値 - 最小) 番目の値を true に変更します。
3. 3 番目のパス: ブール配列の真の値のエントリのインデックス間の差を計算します。

Answer 3

それらをヒープに入れてからO(nlogn)1つずつポップし、ポップしたすべての要素間の最小の差を取得します。最後に、最小限の違いがあります。ただし、より良い解決策があるかもしれません。