在数组中求最大差值的算法
我有一个包含几百万个数字的数组。
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++编写代码，但是用伪代码编写一个很好的算法就可以了。另外，如果我要找的这个号码有名字，我很想知道它是什么。
谢谢。
回答 4
Stack Overflow用户
发布于 2008-09-29 09:07:04
你描述的算法实际上是O(N)，但我认为常量太高了。另一种看起来合理的解决方案是按以下方式使用O(N*log(N))算法：
* 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)我认为它应该更快，因为常量要低得多。
Stack Overflow用户
发布于 2008-09-29 09:14:24
这类问题属于算法的一个分支，称为流算法。它是对问题的研究，这些问题不仅需要O(n)解，而且还需要在一次遍历数据中工作。数据以流的形式输入到算法中，算法不能保存所有的数据，然后数据就永远丢失了。算法需要得到关于数据的一些答案，例如最小值或中位数。
具体地说，您正在寻找流上的窗口中的最大值(或者更常见的是文献中的最小值)。
article上的Here's a presentation，提到这个问题是他们试图达到的子问题。它可能会给你一些想法。
我认为解决方案的轮廓是这样的--在流上维护窗口，在每个步骤中，一个元素被插入到窗口中，另一个元素从另一侧被移除(滑动窗口)。你实际保存在内存中的项目并不是窗口中1000个项目中的所有项目，而是选定的代表，它们将是最小(或最大)的很好的候选者。
阅读这篇文章。这有点复杂，但读了2-3篇之后，你就可以掌握它的诀窍了。
Stack Overflow用户
发布于 2008-09-29 19:38:13
算法思想：
获取数据的前1000个值并对其进行排序
排序中的最后一个-第一个是范围( data + 0，data+ 999)。
然后从排序堆中删除具有值data的第一个元素
并添加元素data1000
现在，排序中的最后一个-第一个是范围( data + 1，data+ 1000)。
重复操作，直到完成
// This should run in (DATA_LEN - RANGE_WIDTH)log(RANGE_WIDTH)
#include <set>
#include <algorithm>
using namespace std;
const int DATA_LEN = 3600000;
double* const data = new double (DATA_LEN);
....
....
const int RANGE_WIDTH = 1000;
double range = new double(DATA_LEN - RANGE_WIDTH);
multiset<double> data_set;
data_set.insert(data[i], data[RANGE_WIDTH]);
for (int i = 0 ; i < DATA_LEN - RANGE_WIDTH - 1 ; i++)
{
range[i] = *data_set.end() - *data_set.begin();
multiset<double>::iterator iter = data_set.find(data[i]);
data_set.erase(iter);
data_set.insert(data[i+1]);
}
range[i] = *data_set.end() - *data_set.begin();
// range now holds the values you seek您可能应该通过1个错误来检查这一点，但是这个想法是存在的。
https://stackoverflow.com/questions/148003
复制相似问题