假设我们有一组数字 P = { p1, p2, p3, ..., pn } ( length(P) = n ) 和选择一个数字作为 q。所以我想找到一个算法来获取集合 P 到 q 最近的成员。所以问题是:什么结构适合保存数据(p1, p2, ...)和算法以在 O(1) 中找到 P 到 q 的最近成员时间复杂度。
最佳答案
- 您无法获得 O(1) 的复杂度。通过使用 van Emde Boas 树，最接近的是 O(lg lg n)。
- 如果集合是静态的，使用排序向量和二进制搜索 (O(lg n)) 找到最近的元素。
- 如果集合可以在查询之间更改，请使用适当的数据结构来维护动态集合(例如，AVL 或红黑树)。
关于algorithm - 最接近数字集的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8262641/