一维最佳近邻数据结构

如果您需要比O(log(n))更快的速度(通过排序数组或二叉搜索树可以很容易地获得),可以使用 van Emde Boas Tree

如果插入时间不相关,那么在排序数组上进行二进制搜索是实现O(logn)查询时间的最简单方法。每次添加一个项目时,对所有内容进行排序。对于每个查询,执行二进制搜索。如果找到匹配项,请将其返回。否则,二进制搜索应该返回该项的索引,即该项应该插入的位置。使用此索引可检查两个相邻的项,并确定其中哪一项更接近查询点。

我假设有O(1)时间的解。我会尽量想一个不涉及太多的内存使用。。。

正如您已经提到的,最快和最简单的方法应该是对数据进行排序,然后查找数据点的左邻居和右邻居。

对列表进行排序,然后使用二进制搜索找到要查找的元素,然后比较左右邻域。可以使用O(1)访问的数组。

比如:

int nearest(int[] list, int element) {

    sort(list);
    int idx = binarySearch(element, list);

    // make sure you are accessing elements that exist
    min = (element - list[idx-1] <= list[idx+1] - element) ? idx-1 : idx+1;

    return list[min];
}

这是O(n logn),如果您要执行许多查找,则将摊销。

使用OCaml Set

module S = Set.Make(struct type t = int let compare = compare end)

let nearest xs y =
  let a, yisin, b = S.split y xs in
  if yisin then y
  else
      let amax, bmin = S.max_elt a, S.min_elt b in
      if abs (amax - y) < abs (bmin - y) then amax else bmin

顺便说一句,你可能会感激我 nth-nearest neighbor sample 从 OCaml for Scientists The F#.NET Journal 文章 Traversing networks: nth-nearest neighbors .