与一组数字最接近的数字

Question

假设我们有一组数字 P = { p1, p2, p3, ..., pn } ( length(P) = n ) 并选择一个数字如q。所以我想找到一种算法来获取集合P中距离q最近的成员。所以问题是：什么结构适合保存数据（p1, p2, ...）和算法以在O(1)中找到 P 到 q 最近的成员时间复杂度。

Answer 1

1. 您无法获得 O(1) 复杂度。通过使用 van Emde Boas 树，您可以得到的最接近的结果是 O(lg lg n)。
2. 如果集合是静态的，则使用排序向量和二分搜索 (O(lg n)) 来查找最近的元素。
3. 如果集合可以在查询之间更改，请使用适当的数据结构来维护动态集合（例如，AVL 或红黑树）。

Answer 2

我能想到获得 O(1) 时间复杂度的唯一方法是使用 O(pn) 空间和 O(pn)对 P 进行预排序并在 pn 大小的数组中分配值的时间。

预排序 P，因此 p1 是最小值，pn 是最大值（我假设它们是整数。）然后存储在大小为 < 的数组中code>(pn-p1+1) 值：

A(p1) = p1
for  i = 2  to  n
    for  q = p(i-1)+1  to  (p(i-1)+p(i))/2
        A(q) = p(i-1)
    for  q = (p(i-1)+p(i))/2  to  p(i) 
        A(q) = p(i)

那么您只需检查某个 q 即可：

if q < A(p1)
    closest = A(p1)
elif q > A(pn)
    closest = A(pn)
else
    closest = A(q)