2
  • 入力: 実数の配列 a[1..n];
  • 出力: 2 つの異なる配列要素間の値の絶対差の最小値。

同じためのブルートフォースアルゴリズムが必要です。

誰でも何か考えがありますか？

4

2 に答える 2

4

要素がソートされている場合、アイテムの各ペアを順番に比較するだけでよい場合があります: [1, 3, 6, 7, 28] -> 7-6 で最小の距離が得られます

力ずくで行うには、各値を他の値 (n*n-1) から減算し、どのペアが最小かを追跡できると思います。同じ要素をそれ自体から減算しないようにする必要がありますが、同じ値を持つ要素はペアとして許容される必要があります。

于 2012-04-20T17:36:54.647 に答える
3

総当たりにしたい場合は、要素のすべてのペアをループするだけです。

min = infinity

for i=1 to n-1
    for j = i+1 to n
        if abs(a[i]-a[j]) < min
            min = abs(a[i]-a[j])

これにはO(n^2)時間がかかります。O(n log n)最初にリストを並べ替えることで、時間を達成できます。

sort(a)
min = infinity

for i = 1 to n-1
    if abs(a[i+1]-a[i]) < min
        min = abs(a[i+1]-a[i])
于 2012-04-20T18:50:15.213 に答える