算法查找的最大差在数字数组 [英] Algorithm for finding the maximum difference in an array of numbers

问题描述

我有几百万的数字数组。

I have an array of a few million numbers.

double* const data = new double (3600000);

我需要遍历数组和找到的范围内（在阵列中的最大值减去最小值）。然而，有一个陷阱。我只是想找到的范围，其中最小和最大的值是1000的样品对方的范围内。

I need to iterate through the array and find the range (the largest value in the array minus the smallest value). However, there is a catch. I only want to find the range where the smallest and largest values are within 1,000 samples of each other.

所以，我需要找到最大：范围（数据+ 0，数据+ 1000），范围（数据+ 1，数据+ 1001），范围（数据+ 2，数据+ 1002），...，范围（数据+ 3599000，数据+ 3600000）。

So I need to find the maximum of: range(data + 0, data + 1000), range(data + 1, data + 1001), range(data + 2, data + 1002), ...., range(data + 3599000, data + 3600000).

我希望这是有道理的。基本上我能做到这一点像上面，但是我正在寻找一个更有效的算法（如果存在）。我觉得上面的算法是O（n），但我觉得这是可能的优化。一个想法，我玩的是保持最新的最大值和最小值，以及如何追溯到他们的轨道，那么只有原路返回的时候有必要的。

I hope that makes sense. Basically I could do it like above, but I'm looking for a more efficient algorithm if one exists. I think the above algorithm is O(n), but I feel that it's possible to optimize. An idea I'm playing with is to keep track of the most recent maximum and minimum and how far back they are, then only backtrack when necessary.

我会在C ++编码这一点，但一个很好的算法，伪code会就好了。另外，如果这个号码，我试图找到了一个名字，我很想知道它是什么。

I'll be coding this in C++, but a nice algorithm in pseudo code would be just fine. Also, if this number I'm trying to find has a name, I'd love to know what it is.

感谢。

推荐答案

您所描述的算法是真的O（N），但我认为不断的太高。另一种解决方案，看起来是合理使用O（N *日志（N））算法的方式如下：

The algorithm you describe is really O(N), but i think the constant is too high. Another solution which looks reasonable is to use O(N*log(N)) algorithm the following way:

* 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)

我相信应该会更快，因为不断的要低得多。

I believe it should be faster, because the constant is much lower.

这篇关于算法查找的最大差在数字数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！