5

以下に示すように、次元m*nのテーブルがあります。

2    6    9    13
1    4    12   21
10   14   16   -1

このテーブルに関するいくつかの制約：

  1. 各行の要素は昇順で並べ替えられます（自然順序付け）。
  2. -1は、セルが計算の目的で重要ではないこと、つまり、そこに要素が存在しないことを意味します。
  3. -1の後に要素を連続して表示することはできません。
  4. すべてのセルは、0からNまでの正の数または-1のいずれかを持つことができます。
  5. 2つのセルが同じ正の数を持つことはありません。つまり、-1は複数回出現できますが、他の数は出現できません。

質問：テーブルからn個の数値のセットSを見つけたいと思います。このセットには、各行の数値が1つだけ含まれている必要があり、max（S）-min（S）は可能な限り小さくなっています。

たとえば、上記の表からS=12,13,14になります。

これが解決できれば本当にありがたいです。私の解決策は複雑で、時間がかかり O(m^n)、これは多すぎます。最適なソリューションが必要です。

4

2 に答える 2

3

O((m*n)^2 * nlog(m))これが私が機能することを証明できるブルートフォースアルゴリズムです：

min <- INFINITY
For each 2 numbers in different rows, let them be a,b
   for each other row: 
        check if there is a number between a and b
    if there is a matching number in every other row:
        min <- min{min,|a-b|}

説明：
aとbの間に数値があるかどうかの確認は、二分探索を使用して実行できます。a 、bにO(logm)
はO((n*m)^2)さまざまな可能性があります。

アイデアは、最大の差を生み出すペアを徹底的にチェックし、それが「実行可能な」ソリューションを提供するかどうかをチェックし（このソリューションの他のすべての要素は範囲[a、b]にあります）、間の差を最小にするペアを取得することです。すべての「実行可能な」ソリューション。

編集：私が提案した2番目の解決策を削除しました。これは貪欲で間違っていました。

于 2012-06-07T11:17:12.337 に答える
2
  1. 各行の最初のすべての要素の位置を優先キュー（最小ヒープ）に入れます。
  2. キューから最小の要素を削除し、同じ行の次の要素に置き換えます。
  3. 「-1」以外の要素が行になくなるまで、手順2を繰り返します。各反復のmax（S）-min（S）を計算し、それが以前の値よりも小さい場合は、これまでの最良のセットSを更新します。

時間計算量はO（m * n * log（m））です。

于 2012-06-07T11:38:08.870 に答える