algorithm - 查找表格中的最小距离

Question

我有一个维度为 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 可以出现多次，但没有其他数字可以。

问题:我想从表中找到一组 S，其中 n 个数字必须包含每行中的一个数字，并且 max(S) - min(S) 尽可能小。

例如上表给出了 S = 12,13,14。

如果能解决这个问题，我将不胜感激。我的解决方案很复杂，需要 O(m^n)，这太多了。我想要一个最优解。

Answer 1

这是我可以证明有效的蛮力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之间是否有数字可以使用二分查找来完成，并且是O(logm)
a,b 有 O((n*m)^2) 种不同的可能性。

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

---

编辑:删除了我提出的第二个解决方案，它贪婪且错误。