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

Question

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

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

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

给定索引i和颜色c，哪个是更接近i且包含颜色c的单元格的索引？

预言机构建算法的复杂度必须为 O(kn)，查询算法的复杂度必须为 O(1)。

编辑

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

---

我的推理

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

V[j] = c

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

ORACLE(array V, int k)

QUERY(array O, int i, int c)

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

Answer 1

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