5

我有一张尺寸为 m * n 的表格，如下所示

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

关于这张表的一些限制：

  1. 每行中的元素按升序排序（自然排序）。
  2. A -1 表示该单元格对于计算而言没有意义，即那里不存在任何元素。
  3. -1 之后的任何元素都不能出现在一行中。
  4. 所有单元格可以具有介于 0 和 N 之间的正数或 -1。
  5. 没有两个单元格具有相同的正数，即 -1 可以出现多次，但没有其他数字可以出现。

问题：我想从表中找到一组包含 n 个数字的 S，其中该集合必须仅包含每一行中的一个数字，并且 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，bO(logm)
有O((n*m)^2)不同的可能性。

这个想法是彻底检查产生最大差异的对，并检查它是否给出了“可行”的解决方案（该解决方案中的所有其他元素都在范围 [a,b] 内），并得到最小化之间差异的对所有“可行”的解决方案。

编辑：删除了我提出的第二个解决方案，这是贪婪和错误的。

于 2012-06-07T11:17:12.337 回答
2
  1. 将每行的所有第一个元素的位置放入优先级队列（最小堆）。
  2. 从队列中删除最小的元素并将其替换为同一行中的下一个元素。
  3. 重复第 2 步，直到某行中不再有与“-1”不同的元素。计算每次迭代的 max(S) - min(S)，如果它小于任何先前的值，则更新迄今为止最好的集合 S。

时间复杂度为 O(m*n*log(m))。

于 2012-06-07T11:38:08.870 回答