c++ - 在给定集合中查找最小值和最大值的算法

Question

一个大型整数数组 array[n] 作为输入给出。给出了两个索引值 - start,end。希望非常快速地找到 - 集合 [start,end] 中的最小值和最大值(包括)和 数组其余部分中的最大值 (不包括 [开始，结束])。

例如-

数组 - 3 4 2 2 1 3 12 5 7 9 7 10 1 5 2 3 1 1

开始，结束 - 2,7

最小值，最大值在 [2,7] -- 1,12

休息时最大 - 10

我想不出比线性更好的了。但这还不够好，因为 n 的阶数为 10^5，并且此类查找操作的数量也是相同的阶数。

如有任何帮助，我们将不胜感激。

Answer 1

我对你的问题的理解是，你想对固定数组进行一些预处理，然后使你的查找最大操作非常快。

此答案描述了一种方法，它执行 O(nlogn) 的预处理工作，然后为每个查询执行 O(1) 的工作。

预处理O(nlogn)

想法是准备两个二维数组 BIG[a,k] 和 SMALL[a,k] 其中

1. BIG[a,k] is the max of the 2^k elements starting at a
2. SMALL[a,k] is the min of the 2^k elements starting at a

您可以通过从 k==0 开始，然后通过将前面的两个元素组合在一起来为每个更高的元素构建值，以递归方式计算此数组。

BIG[a,k] = max(BIG[a,k-1] , BIG[a+2^(k-1),k-1])
SMALL[a,k] = min(SMALL[a,k-1] , SMALL[a+2^(k-1),k-1])

每个查询查找 O(1)

然后，您可以通过组合 2 个预先准备好的答案立即找到任何范围的最大值和最小值。

假设您要查找从 100 到 133 的元素的最大值。 您已经知道从 100 到 131(在 BIG[100,5] 中)的 32 个元素的最大值以及从 102 到 133(在 BIG[102,5] 中)的 32 个元素的最大值，因此您可以找到其中最大的元素以得到答案。

相同的逻辑适用于最小值。您总能找到两个重叠的准备好的答案，它们将结合起来提供您需要的答案。