在表格中寻找最小距离

Question

我有一个大小为m * n的表格如下所示

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

关于这个表的一些限制：

1. 每行中的元素按递增顺序排序（自然排序）。
2. -1表示该单元格在计算目的上没有重要性，即不存在任何元素。
3. -1后面不能出现任何元素。
4. 所有单元格都可以有0到N之间的正数或-1。
5. 没有两个单元格具有相同的正数，即-1可以多次出现，但没有其他数字可以。

问题：我想在表格中找到一个由n个数字组成的集合S，在该集合中每行必须只包含一个数字，并且max(S) - min(S)应尽可能小。

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

如果能解决这个问题，我会非常感激。我的解决方案很复杂，需要O(m^n)的时间，这太多了。我需要一个最优的解决方案。

- dharam

---

在空间、时间或准确性方面，哪一个是最优解？还是全部都是。 - user703016

一个在时间上最优的解决方案。精确性是必须的（即我想要突出显示的东西，对此不会妥协）。 - dharam

@dharam：这是一个有趣的问题。你为什么想要解决它？它是如何出现的？ - Tom Anderson

@Tom：我是一个更大问题的一部分... 这个问题是在一个字符串中找到一个包含字符序列的最小窗口... 例如：考虑一个字符串“abzyxcdcbgahjkcbabghjcbja”，我想找到任何顺序下的序列“abc”。唯一的条件是窗口长度应该最小。对于这个例子，窗口长度为3，序列以cba的顺序出现。 - dharam

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]范围内），并获取使所有“可行”解决方案之间差异最小的一对。

---

编辑：删除我提出的第二种贪心算法，该算法是错误的。

- amit

---

嗨，谢谢您的回复。请看我的思路： 对于第一行中的元素e1，我找到第二行中的元素e2，使得|e1-e2|最小。然后对于e2，在第三行中找到一个元素e3，使得|e2-e3|最小。重复这个过程直到处理完第一行所有的元素，并且你将得到各种包含n个数字的集合。在每个集合中，检查max(s) - min(s)的值。其中最小的值是你要的答案。但如何将其转换为程序是我的实际问题。 - dharam

@dharam：这个解决方案肯定是错误的：line1=5,-1,... ; line2 = 3,6,-1,...; line3= 2,8,-1,...; line4=1,10,-1,...; 建议的解决方案将返回{5,6,8,10}，而最优解是{5,3,2,1}。我建议的第二个解决方案对于这种情况也失败了（我将删除第二个解决方案）。 - amit

我们不考虑-1。 - dharam

@dharam：我知道，看看这个例子——它没有考虑到这一点，而且这是对所提出算法的反例。 - amit

知道了。你绝对是对的。我的解决方案在这种情况下不起作用。我正在尝试编写您的解决方案，但遇到了困难。:( - dharam

Answer 2

1. 将每一行的第一个元素位置放入优先队列（最小堆）中。
2. 从队列中移除最小的元素，并用相同行中的下一个元素替换它。
3. 重复步骤2，直到某一行中没有剩余与“-1”不同的元素。对于每次迭代，计算max(S) - min(S)，如果比之前的任何值都要小，则更新目前为止最佳的S集合。

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

- Evgeny Kluev

---

谢谢。这个解决方案对我已经测试过的几个案例都完美地运行了。感谢您提供这个方案。编码真的很容易。 - dharam