跨多个数组查找最近的元素

Question

假设我有两个数组：

a=[10 21 50 70 100 120];
b=[18 91];

我想匹配a和b中距离最近且在10个单位内的（单个）元素。

结果：

idxa=[1 2 3 4 5 6]

idxb=[2 5]

当匹配元素共享相同的数字时。

我很困惑，因为我不确定如何确保（例如）18与21匹配，而不是与10匹配，因为它们都符合彼此之间在10个单位内的要求。此外，我想在多达8个列表中执行此操作。代码变得过于复杂，我觉得自己错过了一个简单的解决方案。我不担心效率，因为列表的长度很小。

谢谢！

- stuppie

---

如果您在多个列表中执行此操作，您是否总是与同一个进行比较？还是要找到所有三个列表中的“共同”项？另外：在平局的情况下会发生什么？ - Jonas

我想找到所有三个中“共同”的项目。实际数据实际上是小数，因此不应该有并列。如果有，并且它找到了任何一个，就应该采取它。 - stuppie

这对我来说看起来非常像一个最小成本最大二分图匹配问题。它也被称为分配问题。 - Juan Lopes

Answer 1

你的数组似乎已经排序了（我会基于这个假设继续进行；如果没有，你可以简单地对它们进行排序）。

你尝试过将多个数组合并成一个更大的数组吗？（类似于归并排序的合并步骤）。这将是一个很好的起点，因为它将把你的问题简化为“在一个数组中找到最接近的元素”，相比之下这是微不足道的。

这也将允许你删除重复项；即将数组中所有的“21”减少到一个“21”。

为了确保18与21匹配而不是10，你需要计算你的关键值（18）与10个单位范围内的每个值之间的差异（[10,21)），然后选择差异最小的那个。

更新：针对你关于仅查找所有数组共同值的评论，这可以通过在合并数组时找到数组的交集来完成，这实际上可能是一种预定义方法，具体取决于你使用的编程语言。

- Nick Mitchinson

Answer 2

对于小数组，可以通过暴力方法完成：

(1) 迭代两个数组中较小的那个，然后迭代较大的数组
(2) 跟踪“到目前为止最接近的匹配”（CMSF）
(3) 如果找到更好的匹配，请更新CMSF
(4) 当您到达列表末尾时，如果CMSF <= 10，请保留它，否则忽略此项（它没有匹配）

- Tyler Durden

---

如果这些数组已经排序（看起来是的），那么就不需要迭代整个数组。如果CMSF超过了阈值（在本例中为10），则没有必要跟踪它，也没有必要继续查找，在找到一个小于10的CMSF和一个大于10的不同元素后即可停止查找（再次假设数组已排序）。 - Nick Mitchinson