需要找到一个阵列的第一行，其余那些

Question

井之间最低的差异，我已经给定的数对元件(s,h)，其中s发送h元件上的二维数组的第s行的。没有必要每行都有相同数量的元素，只知道一行中不能有多于N个元素。

我想要做的是找到第一行的某个元素与其他元素之间的最小差异（！）。因此，如果我有3行与(101,92) (100,25,95,52,101) (93,108,0,65,200)我想要找到的是3，因为我必须选择92，我有95-92 = 3从第一到第二和93-92 = 1从第一到第三。

我已经达到了一个点，可以肯定的是，如果我有s行，每行n(i)元素和i=0..s，然后n0<=n1<=...<=ns从向别人一号线挑选最适合的时候使其具有良好的平均性能场景。

但是，我不能想办法为O低（N ），或者甚至可能为O（n ）在某些情况下。有没有人有一个相对较好的方式来做到这一点的建议？

Answer 1

将所有行组合到一个列表中，并跟踪哪个元素来自哪里。

对此列表进行排序。

每行有最后一个变量。

对于排序列表中的每个项目，更新适用列表的最后一个变量。如果不是所有的行都有最后一个值，则什么也不做。如果是从第一个列表中的元素：

• 重新计算最后值变量的所有最大的区别。保存这个差异。

如果是从其他列表中的元素：

• 如果所有值都以前没有被设置，计算的最大区别。否则，如果第一个列表的最后一个值与此元素之间的差值大于最大差值，请使用此差异更新最大差异。保存这个差异。

最小的差异是期望值。

实施例：

Lists: (101,92) (100,25,95,52,101) (93,108,0,65,200) 

Sorted 0 25 52 65 92 93 95 100 101 101 108 200 
Source 2 1 1 2 0 2 1 1 0 1 2 2 

Last[0] - - - - 92 92 92 92 101 101 101 101 
Last[1] - 25 52 52 52 52 95 100 100 101 101 101 
Last[2] 0 0 0 65 65 93 93 93 93 93 108 200 

Diff - - - - 40 41 3 8 8 8 7 9 
Best - - - - 40 40 3 3 3 3 3 3 

最佳= 3作为必需的。存储实际物品或事后查找应该很容易。

复杂性：

让n是项目总数和k是列表的数目。

O(n log n)用于组合+排序。

O(nk)（最坏的情况下）扫描通过，因为我们检查n项目，并在每个项目，我们做最大O(k)工作。因此O(n log n + nk)。