找到表格中的最小距离

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可以多次出现,但没有其他数字可以.

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

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

如果能解决这个问题我真的很感激.我的解决方案很复杂,需要花费 O(m^n)太多.我想要一个最佳解决方案.

Answer 1

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

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