0

この整数のリストがあるとします：

リスト A = 3 5 9 10 11 15

他にも整数のリストがいくつかあるとします。

リスト B1 = 1 2 3 4 5 6 7 8 20 25

リスト B2 = 4 7 8 13 17

リスト B3 = 10 11 12 13 14 15 16 17

注:

  • Aでは、4はギャップです（6、7、8、12、13、14と同じ）
  • B1では、1、2、20、および25が脂肪です : Aの最小値より劣る、またはAの最大値より優れているため、余分です

次のようなアルゴリズムはありますか?

  1. B リストが A リストのすべてのギャップを埋めるかどうかを示します。
  2. (いくつかのギャップが埋められていない場合) どの B リストが A リストのギャップを埋めているかを示します。最高= 埋められたギャップの最大数と脂肪の最小数

私はそれが古典的な必要性だと思います...

ps : 私は .py コードを好みますが、疑似コードは問題ありません

どうもありがとう

4

2 に答える 2

0

A と B の並べ替えられた配列に対して 2 つの反復子を使用します。1 つ目は A を反復し、2 つ目は B を反復します。A にギャップがある場合は常に、B の次の数値でそれを埋めなければなりません。このように (C# の例):

var iterA = A.Sort().GetEnumerator();
var iterB = B.Sort().GetEnumerator();

iterA.MoveNext(); iterB.MoveNext();
var prevA = iterA.Current;
var curB = iterB.Current;

if (curB < prevA) return "B is fat";

while (iterA.MoveNext()) {
  var curA = iterA.Current;
  if (curA - prevA == 1) {
    prevA = curA;
    continue; // no gap
  }
  while (curA - prevA > 1) {
    if (curB != prevA + 1) return "B does not fill gap";
    if (iterB.MoveNext()) {
      curB = iterB.Current;
      prevA++;
    } else return "B does not fill gap";
  }
  prevA = curA;
}

ランタイムの複雑さは線形 O(N) で、N は min(A) と max(A) の間の数値です。これは、この問題にアプローチする方法についてのアイデアを提供するための単なる例です。このアルゴリズムの正確性は保証しません。コンパイルもテストもしていません。Python についてはわかりませんが、C# のイテレータに似たものを提供していると思います。

于 2013-06-13T07:27:36.033 に答える