需要找到一個陣列的第一行，其餘那些

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)。