我想要一个数据结构,它可以存储自然数的 n 2D 点 (x,y) 的列表,然后允许在 O(1) 复杂度时间内检查给定点是否存在于原始点列表中,这个时间复杂度应该是确定性(这意味着哈希表不是一个选项)。该数据结构的创建也应该尽可能高效。我无法使用需要在时间复杂度上进行一些初始化的数据结构,这比 O(n * sqrt(n)) 更糟糕。
是否存在这样的数据结构?
最佳答案
是的,它确实存在。
首先,让我们考虑 O(1)
的第一个候选者。包含操作。第一个自然候选者是二维数组。问题在于另一个约束,即初始化时间复杂度必须为 O(n*sqrt(n))
.
如果我们不初始化值怎么办?我们可能对这些存储单元中已经存在的随机垃圾感到满意,并通过设置 arr[x][y]
在数组中标记一个点。为 1 或任何其他值。
不幸的是,这可能会以很小的概率导致误报,但我们无法初始化 arr
为零,因为需要 O(n^2)
.
幸运的是,存在常量数组初始化的算法。稍后我将在这里描述它,但现在,您可以阅读 here
算法描述
让我们有一个数组point_filter
尺寸MAX_INT x MAX_INT
还有两个该大小的数组。我们称它们为FROM
和TO
。我们还需要一个指标 TOP
初始化为0。
point_filter: array MAX_INT x MAX_INT
FROM: array MAX_INT x MAX_INT
TO: array MAX_INT x MAX_INT
TOP: 0
我们假设数组中的所有值都是无符号整数。
我们会说 point_filter
的元素 i已经被访问过当且仅当FROM[i] < TOP and TO[FROM[i]] = i
如果满足上述条件,则point_filter[i]
的值返回初始值(假设为 0),否则返回。
设置point_filter
第一次做:
FROM[i] = TOP
TO[TOP] = i
point_filter[i] = 1 //visited, point in filter
TOP++
这样,point_filter
的初始化就完成了需要O(1)
。话说,那一点i
在集合中,只需按照上述步骤操作即可,并且要检查该点之前是否插入过,只需检查是否 FROM[i] < TOP and TO[FROM[i]] = i
.
现在您需要调整二维数组的算法,这非常简单。只需替换 [i]
与 [i][j]
并且该算法仍然有效。
关于algorithm - 是否有一种数据结构用于存储自然数的 2D 点,允许检查 O(1) 中是否存在?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58948978/