问列表中的相似元素
EN

Stack Overflow用户

提问于 2011-06-09 04:26:25

回答 1查看 38关注 0票数 0

对于给定的N个列表，每个列表中有M个数字，我们必须从每个组中找到一个元素，这样每对ai aj给|ai-aj|的值越小越好。

例如，我们有3个列表

{12,16,67,43}

{7,17,68,48}

{14,15,77,54}

为了最小化结果，我们必须从列表1中选择数字16，从列表2中选择数字17，从列表3中选择数字15，所以

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

所以我们的结果是:2

如何快速解决这个问题？在N*M时间内？或者记录一些时间

克里斯

发布于 2011-06-09 05:40:05

如果使用线性搜索，则对于一个匹配，复杂度为O(N*M) (即，对于集合j中的每个元素，对集合i中最相似的项进行线性搜索，并选择这些结果中最小的一个。

如果首先对每个集合进行排序，您将得到(至少) O(N log N)+O(M log M)用于排序，O(M log N)用于搜索(其中N是集合i中的元素数，M是集合j中的元素数)。如果您一起遍历这两个集合，您可能可以将组合搜索的结果减少到O(N + M)。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/6284821

复制

相似问题

问列表中的相似元素EN