列表中的類似元素

Question

每個列表中給定N個M列表，我們必須從每個組中找到一個元素，例如 每對ai aj給出| ai-aj |儘可能小。

例如 我們有3所列出

{12,16,67,43} 

{7,17,68,48} 

{14,15,77,54} 

並最小化結果，我們必須從列表1 號碼17從列表2 號碼15從列表3 所以

|16-17|=1 
|16-15|=1 
|17-15|=2 

挑 數16

所以我們的結果是：2

如何解決我快嗎？在N * M時間？或者登錄一些時間

克里斯

Answer 1

如果使用線性搜索，複雜度爲O（N * M）爲一個匹配（即，在集合的J每個元素，最相似的做線性搜索如果你排序每個集合，你會得到（至少）O（N日誌N）+ O（M日誌M）爲排序，和O （M log N）（其中N是集合i中元素的數量，M是集合j中元素的數量）。如果你通過兩個集合，你可以將它們減少到O（N + M ）用於組合搜索。