请教一个算法/方案？

[zxCoder]

有三个集合，集合里是一些可以度量相似度的东西，比如一个数，可以用绝对值来衡量相似情况，又比如一个向量，大概就是这个意思，数学上应该有比较正式的定义。。。

有没有一种比较好的方案，可以找出三个集合中，有哪些二元组或者三元组，对应是比较相似的。

比如以整数集合为例

A (1,2,3) B (1,100) C (10,4,3)

假设以绝对值来衡量，相似的阈值设为 2

那么就有

(A0 B0 C2) (A1 B0 C2) (A1 C1) (A2 C1)

等等

[ipwx]

最好的算法不清楚。

使用 Ball-tree 配合应该能有复杂度 O(N log N) 的算法， 但是常数较大。具体方法就是对 ABC 三个集合建 Ball-tree ，然后 ABC 分别枚举每一个元素，在另外两个 Ball-tree 找 distance < threshold 的点，最后用 hashtable 对三元组去重。

目测最优算法也是 O(N log N) 的，但是常数比这个小。

[ipwx]

哦一维情况下可以对三个集合先排序，然后用二分查找代替建树。

[ipwx]

Ball-tree implementation： https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html#sklearn.neighbors.BallTree.query_radius