java - 如何在未排序的数组中找到最接近的 double

Question

我在离散空间中有一组点，坐标以 N 个 double[] 数组的形式给出。

如:

点 T1 = {1.3,2.5,4-3} ---> double[] x = {1.3}, double[] y = {2.5}, double[] z = {4.3}

然后我有一个函数，它在连续空间的所有方向上从给定点生成偏移量，我需要在我的矩阵/ double 组中找到最接近的匹配。

问题是我无法对这些数组进行排序并应用二进制搜索，因为 Point 的组件在排序后很可能没有相同的索引，相对于彼此而言。

是否有一些数据结构/算法可以用来避免迭代搜索最接近的匹配点？

将点组织成一个数组实例描述整个点而不是每个组件的数组会更好吗？

编辑

看起来理想的解决方案是使用评论中建议的 k-d 树。计算机科学算法不是我的领域，因此在我研究该主题时，用 k-d 树或其他替代方法展示最小示例的答案将是最有帮助的。

Answer 1

如果我理解你的问题，你有 N 个大小为 M 的 float 数组，每个数组包含一个点在 N 维空间中沿轴的坐标。您还有一个 float ，您想要找到 float 最接近其中一个分量的点的索引。如果这是正确的，我会创建一个单一的数组，其元素是对(值，索引)，其中值是组件之一，索引带来组件所属点的索引。然后，您可以使用值作为 sorting.key 对数组进行排序。那时您可以使用 float 进行二进制搜索。

当然，只有当您有多个 float 要搜索时，构建和排序数组才有意义，因为排序将花费 O (K log K)，其中 K= N*M，然后搜索将花费 O (log K ).如果只需要查找一个 float ，还不如对数组进行全量查找，时间复杂度为O(K)。