3

アルゴリズムの問​​題があります。k セットの整数 > 0 (必ずしも同じサイズではない) が与えられた場合、最大値と最小値の差が最小になるように、各セットから k 個の数値を 1 つ選択する必要があります。例: k=5

セット 1:89 45 22 16

セット 2:89 34

セット 3:37 62 89

セット 4:89 96

セット 5:89 91 94

答え: すべてのセットの差 0 から 89 を選びます。

例 2 (より難しい) k=5

セット 1:12 19 44 52 59 100

セット 2:35 60 90 94 98 101

セット 3:48 49 57 64 78 90

セット 4:15 38 56 90 97

セット 5:54 58 59 89 202

答え: k 個の要素を選択:52,60,57,56,54) 差 60-52=8.

アプローチ方法に関する提案はありますか？

4

1 に答える 1

2

次のように実行できます。

  • setUnionすべてのセットの和集合で構成する
  • currentBest和集合の最大要素と最小要素の間の距離の差を初期化します
  • の各要素についてsetUnion、元のKセットを調べて、それ以上で最も近い要素を見つけます。までの数のセットになりKます。minそれらのとを見つけて、違いmaxと照合しますcurrentBest
  • 完了currentBestすると、あなたの問題に対する答えが得られます。

和集合のサイズが で、セットにN順序付き表現を使用する場合K、このアルゴリズムは時間内に答えを見つけますO(N*K*LogN)。

于 2013-04-11T15:59:54.340 に答える