algorithm - 动态范围搜索

Question

<分区>

Answer 1

我不确定这是否会实现您想要的，但这是一次尝试。它将涉及 O(n) 预处理步骤，作为返回，将为任何给定的查询提供 O(1) 运行时间的机会，以平衡空间复杂性(通过参数 c)。如果您的 rangeList 经常更改，这可能没有帮助。

预处理步骤:

1. 找到范围列表的“总范围”(可接受的最低值和最高值，尽管两者之间会有差距)。 O(1)

2. 选择浓度参数 c(整数)作为您希望在该范围内评估的点数。 O(1)

3. 创建一个映射函数，将整数 [1, c] 映射到步骤 1 中找到的总范围，也可以进行逆运算(这并不比摄氏-华氏转换复杂)。也是 O(1)

4. 利用映射函数，确定总范围内对应[1,c]的点。扫描范围列表，边走边评估这些点，将答案((True, (300, 2000)))存储在长度为 c 的数组中(我们称该数组为“已评估”)。 O(n+c)

收到查询后:

1. 利用映射函数将查询数在“总范围”->[1,c]方向进行转换。如果转换后的数字超出 [1, c] 范围，则返回 (False, None, None)。 O(1)

2. 取转换后数字的上限和下限，得到两个整数 a 和 b。比较 Evaluated[a] 和 Evaluated[b]。如果它们包含相同的答案，则返回它(如果您转换后的数字已经是整数，则直接返回 Evaluated[converted number])。 O(1)

3. 如果 Evaluated[a] 和 Evaluated[b] 给出不同的答案，则必须进行二分查找。但是您至少可以在 a 和 b 之间的中间开始搜索，映射回“总范围”。