7

假设我有四组

A [ 0, 4, 9]

乙 [ 2, 6, 11]

C [ 3, 8, 13]

D [ 7, 12 ]

现在我需要每个组中的一个数字（即一个新组）E [A 的数量，B 的数量，C 的数量，D 的数量]，这样 E 中的最大数量和 E 中的最小数量之间的差异应该是可能最低。这是什么类型的问题？哪种图算法会更好地解决这类问题？提前致谢。

PS：我正在尝试在 java 中解决这个问题，并对未指定的标题感到抱歉。

编辑：最后我找到了我真正想要的http://rcrezende.blogspot.in/2010/08/smallest-relevant-text-snippet-for.html

4

2 回答 2

4
  1. 将每个组的内容组合成一个数组。数组的每个元素应该是一对（数字，组名）。
  2. 按数字对该数组进行排序。
  3. 一个接一个地推进两个迭代器。当不是每个组的元素都在这些迭代器之间时，移动第一个迭代器。当这些迭代器之间的每个组中都有一个元素时，移动第二个迭代器。有关详细信息，请参阅此问题。
  4. 迭代器之间的最小距离决定了最佳结果组（当同一组有多个代表时，您只需要删除不需要的元素）。

其他算法：

  1. 对每个组的元素进行排序（如果尚未排序）。
  2. 将每个组的最小元素的一对（编号，组名）放入优先级队列（最小堆，优先级=编号）。
  3. 从队列中删除最小的元素并将其替换为同一组中的下一个元素。
  4. 重复步骤 3，直到某个组中没有更多元素。计算每次迭代的 max(queue) - min(queue)，如果它小于任何先前的值，则更新迄今为止最好的结果组。
于 2012-08-25T17:34:20.337 回答
2

我认为您可以进行详尽的搜索，并快速终止，这并不像看起来那么糟糕。

例如，如果您从 A 和 B 中选择一个数字，您可以从 C 中选择两个最接近这两个数字的数字，使用任何其他数字都不会产生更好的结果。

  • 对于 A 的每个元素：调用它a，您正在寻找一个接近区间 (a,a) 的数字
  • 现在为每个组选择最接近的数字（您可以使用二进制搜索来完成）。现在你有了一个新的搜索区间，要么是 (a,b1) 要么是 (b2,a)

例子：

  • 从 A 中选择 4，搜索接近 (4,4)
  • A) 从 B 中选择 2，搜索接近 (2,4)
  • .... 从 C 中选择 3，它在区间内。搜索接近 (2,4)
  • .... 从 D 中选择 7，区间为 (2,7)，距离为 5。
  • B) 从 B 中选择 6，搜索接近 (4,6)
  • ……
于 2012-08-25T17:37:58.073 回答