1

输入一个大array[n]整数数组。给出了两个索引值 - start,end。希望非常快速地找到- min & max in the set [start,end]（包括）和max in the rest of array（不包括 [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 is of order 10^5此类查找操作的数量也是相同的顺序。

任何帮助将不胜感激。

4

8 回答 8

6

我理解您的问题的方式是您想对固定数组进行一些预处理，然后使您的 find max 操作非常快。

该答案描述了一种方法，该方法执行 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 的元素的最大值。您已经知道 32 个元素的最大值 100 到 131（在 BIG[100,5] 中）以及从 102 到 133 的 32 个元素的最大值（在 BIG[102 ,5]) 所以你可以找到其中最大的一个来得到答案。

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

于 2013-05-04T08:44:51.590 回答
3

恐怕没有更快的方法了。您的数据是完全随机的，因此您必须遍历每个值。即使排序也无济于事，因为它充其量是 O(n log n)，所以它比较慢。你不能使用二分法，因为数据没有排序。如果您开始构建数据结构（如堆），它最多也将是 O(n log n)。

于 2013-05-04T07:59:13.803 回答
3

您需要一种数据结构，可以快速回答数组上的间隔的最小和最大查询。

您想在输入数组上构建两个段树；一个用于回答间隔最小查询，一个用于回答间隔最大查询。这需要线性预处理、线性额外空间，并允许查询占用对数时间。

于 2013-05-04T08:42:11.330 回答
2

如果数组非常大，则将其拆分为分区并使用线程对每个分区进行线性检查。然后用线程的结果做最小/最大。

于 2013-05-04T08:01:43.550 回答
1

在未排序的数组中搜索最小值和最大值只能通过一次取两个值并首先将它们相互比较来优化：

register int min, max, i;
min = max = array[0] ;

for(i = 1; i + 1 < length; i += 2)
{
    if(array[i] < array[i+1])
    {
        if(min > array[i]) min = array[i];
        if(max < array[i+1]) max = array[i+1];
    }
    else
    {
        if(min > array[i+1]) min = array[i];
        if(max < array[i]) max = array[i+1];
    }
}

if(i < length)
    if(min > array[i]) min = array[i];
    else if(max < array[i]) max = array[i];

但我不相信它实际上更快。考虑在汇编中编写它。

编辑：比较字符串时，此算法可能会有所作为！

于 2013-05-04T08:36:41.710 回答
0

如果您知道最小值，则可以从 x 到 min 测试该值是否存在于数组中。如果你有点知道最大值，你可以从 y 到最大值测试（向后），如果值存在于数组中，你会找到最大值。

例如，从您的数组中，我假设您只有正整数。：

array - 3 4 2 2 1 3 12 5 7 9 7 10 1 5 2 3 1 1

您将 x 设置为 0，测试是否存在 0，不存在，然后将其更改为 1，您会找到 1。有您的最小值。您将 y 设置为 15（任意大数）：存在吗？不。设置为 14。存在吗？不，设置为 13。存在吗？不。设置为 12。存在吗？是的！有你的最大值！我只是做了4个比较。

如果 y 从第一次尝试就存在，您可能已经测试了数组内部的值。所以你用 y + length / 2 再次测试它。假设你找到了数组的中心，所以贴一点。如果再次找到第一次尝试的值，它可能在数组中。

如果您有负值和/或浮点值，则此技术不起作用:)

于 2013-05-04T08:05:38.053 回答
0

当然，不可能有次线性算法（据我所知）来搜索你想要的方式。但是，在某些情况下，您可以通过存储固定的最小值-最大值范围来实现次线性时间，并且通过对范围的一些了解，您可以改善搜索时间。例如，如果您知道搜索的“大部分”时间范围是 10，那么您可以分别存储 10/2 = 5 个元素的 min-max 并索引这些范围。在搜索期间，您必须找到可以包含搜索范围的范围超集。

例如在示例数组中 - 3 4 2 2 1 3 12 5 7 9 7 10 1 5 2 3 1 1

开始，结束 - 2,7

[2,7] 中的最小值、最大值 -- 1,12

如果您“知道”大部分时间搜索范围将是 5 个元素，那么您可以预先索引 min-max，例如：因为 5/2 = 2，

0-1  min-max (3,4)
2-3  min-max (2,2)
4-5  min-max (1,3)
6-7  min-max (5,12)
...

我认为，当范围很大时，这种方法会更好地工作，以便存储 min-max 避免一些搜索。

要搜索 min-max [2-7]，您必须搜索存储的索引，例如：2/2 = 1 到 7/2 = 3，然后 mins(2,1,5) 中的 mins(2,1,5) 将为您提供最小值 (1)最大值（2,3,12）的最大值将为您提供最大值（12）。如果重叠，您将只需要搜索角索引（线性）。我认为它仍然可以避免几次搜索。

这个算法可能比线性搜索慢（因为线性搜索有很好的参考局部性）所以我建议你先测量它们。

于 2013-05-04T08:21:24.263 回答
-1

线性是你能做的最好的，而且它相对容易证明。

假设无限量的瞬时内存存储和无成本访问，这样我们就可以忽略它们。

此外，我们将假设您在子字符串中查找最小值/最大值的任务。我们会将它们视为本质上完全相同的机械问题。一个只是神奇地跟踪比较中小于其他数字的数字，一个神奇地跟踪比比较中更大的数字。假定此操作是无成本的。

然后让我们假设子数组问题的最小值/最大值，因为它与任何数组的最小值/最大值问题相同，我们将神奇地假设它已解决，并且作为我们寻找更大数组中的最大值。我们可以假设整个数组中最大的数实际上是我们看到的第一个数字，它也是子数组中的最大数，也恰好是数组中的最小数。子阵列，但我们只是不知道我们有多幸运。我们怎样才能知道？

我们要做的最少的工作是将它与数组中的所有其他数字进行比较，以证明它是最大/最小的。这是我们假设的唯一行动是有代价的。

我们需要做多少比较？我们将 N 设为数组的长度，任何长度 N 的操作总数为 N - 1。当我们向数组中添加元素时，比较的数量以相同的速率扩展，即使我们所有的广泛离谱的假设成立。

因此，我们已经到达了这样一个点，即 N 既是数组的长度，也是在我们极其不切实际的最佳情况下，最佳可能操作的成本增加的决定因素。

在最佳情况下，您的操作会随 N 扩展。对不起。

/sorting 输入必须比这个最小操作更昂贵，因此它仅适用于您多次执行操作并且无法存储实际结果的情况，这似乎不太可能，因为 10^5 个答案不完全征税。

//多线程之类的也很好，只需假设这样做的任何成本，然后将N除以线程数。然而，最好的算法仍然可以线性扩展。

///我猜它实际上必须是一个特别奇怪的现象，因为在不假设数据的情况下，任何东西都可以比线性更好地扩展......stackoverflowers？

于 2013-05-04T09:32:53.277 回答