列表中的类似元素

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 ）用于组合搜索。