重新创建一个 O(n*k) 算法来计算 θ(n)

Question

您有 2 个 int[] 数组，输入长度相同 - x、k。

数组 x 中的每个元素告诉您给定索引的功率级别。

数组 k 中的每个元素告诉您从数组 x 中选择的功率级别数（包括其自身）。

这些是数组的条件：

(∀i ∈ {1, . . . , n − 1})(1 ≤ ki+1 ≤ ki + 1)

尝试返回 ki 定义的 x 中每个组的最强索引的索引 (j)。 x

j =max{xs |i−ki <s≤i}

，时间复杂度为 θ(n)，其中 n 是数组的长度。

我提出了一个简单的解决方案，即 O(n*k)，其中 k 表示使用 max() 来查找每个子数组中的最大数字：

"""
    (∀i ∈ {1, . . . , n − 1})(1 ≤ ki+1 ≤ ki + 1)
    max{xs |i−ki < s ≤ i}
"""
x = [1000, 4, 3, 2, 500, 10, 1]
k = [1, 2, 2, 3, 2, 3, 1]

for i in range(len(x)):
    group = max(x[i - k[i] + 1 : i - k[i] + 1 + k[i]])
    print(x.index(group), end=" ")

代码块中输入的正确输出是：

0 0 1 1 4 4 6

x1 -> k1 == 1: we are only choosing from x1(1000) -> in that case we return the first index
x2 -> k2 == 2: we are choosing from x1, x2(1000, 4) -> first index is larger so we return it
x3 -> k3 == 2: x2, x3 -> second index is the largest
x4 -> k4 == 3: x2, x3, x4 -> second index is the largest
x5 -> k5 == 2: x4, x5
x6 -> k6 == 3: x4, x5, x6
x7 -> k7 == 1: x7

也许可以通过队列来完成？

Answer 1

当数组 k 的输入通常被视为变量时，断言在 O(1) 中访问子列表的最大值是可行的是具有挑战性的。您的情况是范围最大查询问题，其中增强查询时间可能涉及以 O(log n) 访问子列表中的最大值，这会给您带来 O(k*log(n)) 最坏情况的总体情况。参考线段树资源来理解范围查询问题。

要使用线段树来解决您的问题，您可以参考此链接：Range Range Max Query Problem