arrays - 数据结构 “oracle” 能够在 O(1) 中回答查询

Question

设V 是一个包含n 元素的向量，其中每个单元格可以包含k 种可能的颜色之一，即

V[i] ∈ {c1. . . ,ck}

设计一个算法，在给定 V 的情况下，构造一个能够在 O(1) 中回答以下类型查询的“oracle”(一种数据结构):

给定一个索引 i 和一个颜色 c，这是距离 i 更近且包含颜色 c 的单元格的索引？

oracle构造算法复杂度在O(kn)，查询算法在O(1)。

编辑

O(kn) 涉及时间复杂度，因此额外内存没有限制。

---

我的推理

给定 i 和 c，查询应返回索引 j 和

V[j] = c

最小化 |我 - j |。如果没有包含颜色 c 的单元格，则它必须返回 -1。所以我猜这两个函数的原型(prototype)应该是这样的:

ORACLE(array V, int k)

QUERY(array O, int i, int c)

数组 O 由 oracle 函数创建，以便“保存”预处理值，这些值随后将由函数查询在 O(1) 中外推。我被困在这段话里，因为我不明白如何放置值才能得到正确的结果。有什么提示吗？

Answer 1

正如您所说，您的 oracle 可能应该是一个 NxK 数组，每个索引和每种颜色的答案都存储为一个整数索引，该索引使索引接近具有查询颜色的查询索引。将您的 oracle 数组初始化为全 -1。然后通过你的数组 V 首先向前，然后向后。当您向前浏览时，只需跟踪 V 中的最后一个索引，您在其中看到每种颜色 k 的颜色 k(如果您还没有看到颜色，则为 -1)，然后当您按正向顺序浏览 V 时，如果你在索引 i，那么颜色 j 的 oracle 的答案是你看到颜色 j 的最后一个索引。然后向后遍历数组 V，并记录您最后一次看到每种颜色的时间。当您位于数组 V 中的位置 j 时，检查向前移动时每种颜色最近的单元格的索引是什么，以及当您向后移动时看到颜色时最后一个单元格的索引是否更接近，然后用更接近的索引覆盖 oracle 单元格。在向前和向后遍历数组后，您将在 O(1) 时间内完全构建 oracle 并准备好进行查询。