oco*_*or0 15 algorithm data-structures
我有一种情况,我需要找到最接近我请求的键的值.它有点像最近的地图,它定义了键之间的距离.
例如,如果我在地图中有键{A,C,M,Z},则对D的请求将返回C的值.
任何的想法？
Gus*_*uss 15
大多数树数据结构使用某种排序算法来存储和查找密钥.许多这样的实现可以找到你所探测的密钥的密钥(通常它最接近下方或最接近上方).例如,Java TreeMap实现了这样的数据结构,您可以告诉它为您提供查找键下方最近的键,或查找键上方最近的键(higherKey和lowerKey).
如果你可以计算出距离(它并不总是那么容易 - Java的接口只需要你知道,如果任何给定的关键是"低于"或"高于"其他任何给定的键),那么你可以要求上述两个最接近和下方最接近然后计算你自己哪一个更近.
您的数据的维度是什么？如果它只是一维,则排序数组将执行此操作 - 二进制搜索将找到完全匹配和/或显示搜索关键字所在的两个键之间 - 并且一个简单的测试将告诉您哪个更接近.
如果您不仅需要找到最近的键,而且需要找到一个关联的值,请维护一个相同排序的值数组 - 键数组中检索到的键的索引就是值数组中值的索引.
当然,有许多替代方法 - 使用哪种方法取决于许多其他因素,例如内存消耗,是否需要插入值,是否控制插入顺序,删除,线程问题等等...