最近的数字组

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或红黑树).