首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在数组中求最大差值的算法

问在数组中求最大差值的算法
EN

Stack Overflow用户
提问于 2008-09-29 08:55:56
回答 7查看 6.6K关注 0票数 18

我有一个包含几百万个数字的数组。

代码语言:javascript
复制
double* const data = new double (3600000);

我需要遍历数组并找到范围(数组中的最大值减去最小值)。然而,这里有一个问题。我只想找出最小值和最大值在1000个样本内的范围。

所以我需要找到最大值: range(data + 3599000,data + 1000),range(data + 1,data + 1001),range(data + 2,data + 1002),...,range(data +3599000,data +1001)。

我希望这是有意义的。基本上我可以像上面那样做,但我正在寻找一个更有效的算法,如果有的话。我认为上面的算法是O(n),但我觉得它是可以优化的。我正在尝试的一个想法是,跟踪最新的最大值和最小值,以及它们的后退距离,然后在必要时才回溯。

我将用C++编写代码,但是用伪代码编写一个很好的算法就可以了。另外,如果我要找的这个号码有名字,我很想知道它是什么。

谢谢。

EN

回答 7

Stack Overflow用户

回答已采纳

发布于 2008-09-29 09:07:04

你描述的算法实际上是O(N),但我认为常量太高了。另一种看起来合理的解决方案是按以下方式使用O(N*log(N))算法:

代码语言:javascript
复制
* create sorted container (std::multiset) of first 1000 numbers
* in loop (j=1, j<(3600000-1000); ++j)
   - calculate range
   - remove from the set number which is now irrelevant (i.e. in index *j - 1* of the array)
   - add to set new relevant number  (i.e. in index *j+1000-1* of the array)

我认为它应该更快,因为常量要低得多。

票数 8
EN

Stack Overflow用户

发布于 2008-09-29 09:14:24

这类问题属于算法的一个分支,称为流算法。它是对问题的研究,这些问题不仅需要O(n)解,而且还需要在一次遍历数据中工作。数据以流的形式输入到算法中,算法不能保存所有的数据,然后数据就永远丢失了。算法需要得到关于数据的一些答案,例如最小值或中位数。

具体地说,您正在寻找流上的窗口中的最大值(或者更常见的是文献中的最小值)。

article上的Here's a presentation,提到这个问题是他们试图达到的子问题。它可能会给你一些想法。

我认为解决方案的轮廓是这样的--在流上维护窗口,在每个步骤中,一个元素被插入到窗口中,另一个元素从另一侧被移除(滑动窗口)。你实际保存在内存中的项目并不是窗口中1000个项目中的所有项目,而是选定的代表,它们将是最小(或最大)的很好的候选者。

阅读这篇文章。这有点复杂,但读了2-3篇之后,你就可以掌握它的诀窍了。

票数 10
EN

Stack Overflow用户

发布于 2008-09-29 09:21:27

这是一个很好的最小队列的应用-一个队列(先进先出=先进先出),它可以同时跟踪它所包含的最小元素,并具有分期不变的更新。当然,max-queue基本上也是一样的。

一旦有了这个数据结构,就可以考虑将CurrentMax (过去的1000个元素)减去CurrentMin,将其存储为BestSoFar,然后推送新值并弹出旧值,然后再次检查。这样,不断更新BestSoFar,直到最终的值是您问题的解决方案。每一步都需要分期不变的时间,所以整个过程是线性的,而且我所知道的实现有一个很好的标量常量(它很快)。

我不知道关于min-queue的任何文档--这是我和一个同事合作提出的一种数据结构。您可以通过在内部跟踪数据的每个相邻子序列中最少元素的二叉树来实现它。它简化了只从结构的一端弹出数据的问题。

如果您对更多细节感兴趣,我可以尝试提供它们。我想把这个数据结构写成一篇论文写给arxiv。还要注意的是,Tarjan和其他人以前得到了一个更强大的min-deque结构,可以在这里工作,但实现要复杂得多。你可以在google for "mindeque"上阅读关于Tarjan et al.的工作。

票数 6
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/148003

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档