Joh*_*ohn 5 java arrays algorithm optimization search
我在离散空间中有一组点,坐标以N double []数组的形式给出.
如:
点T1 = {1.3,2.5,4-3} ---> double [] x = {1.3},double [] y = {2.5},double [] z = {4.3}
然后我有一个函数,它在连续空间的所有方向上从给定点生成偏移量,我需要在我的矩阵/双数组中找到最接近的匹配.
问题是我无法对这些数组进行排序并应用二进制搜索,因为Point的组件很可能在排序后没有相同的索引.
是否有一些数据结构/算法可以应用于避免迭代搜索最接近的匹配点？
组织点是否更好,以便有一个数组实例描述整个点而不是每个组件的数组？
编辑
看起来理想的解决方案将使用评论中建议的kd树.计算机科学算法不是我的领域,因此在我研究该主题时,用kd树或其他替代方案展示最小例子的答案将是最有帮助的.
如果我理解你的问题，你有 N 个大小为 M 的浮点数数组，每个数组都包含 N 维空间中沿轴的点的坐标。您还有一个浮点数，并且您想要找到该浮点数最接近其中一个组件的点的索引。如果这是正确的，我将创建一个数组，其元素是对（值，索引），值是组件之一，索引带来组件所属点的索引。然后，您可以使用 value 作为 sorting.key 对数组进行排序。此时您可以使用浮点数进行二分搜索。
当然，只有当您有多个浮点数要搜索时，构建和排序数组才有意义，因为排序将花费 O (K log K)，其中 K= N*M，而之后的搜索将花费 O (log K)。如果只需要搜索一个浮点数，那么不妨对数组进行一次完整搜索，时间复杂度为 O(K)。