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

以下步骤将完成

1) Store the gaps of A, in an array.
2) Then Map each element of A With different B(B1,B2,..)
3) And then display the result, based on the result in the above step

这是解决此问题的蛮力方法。

于 2013-06-12T21:55:50.763 回答
0

我会在 A 和 B 的排序数组上使用两个迭代器。第一个迭代 A,第二个迭代 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 回答