1

假设我们有以下一组数字表示随时间变化的值

1 2 3 10 1 20 40 60

现在我正在寻找一种算法来找到从一次到另一次的最高百分比增长。在上述情况下，答案将是一对 (1, 60)，它增加了 6000%。

到目前为止，我能想到的最好的算法是蛮力方法。我们使用一系列迭代来考虑所有可能的对：

第一次迭代：

1-2 1-3 1-10 .. 1-60

第二次迭代

 2-3 2-10 2-1 ... 2-60

（ETC。）

这具有复杂度 O(n 3 )。

我也一直在考虑另一种方法。找出所有严格递增的序列，并仅确定这些严格递增的序列中的百分比增长。

你们还有什么其他想法吗？如果我的想法是错误的，请纠正我！

4

4 回答 4

2

我可能误解了这个问题，但似乎你想要的只是最大和最小的数字，因为这两个数字很重要。

while true:
    indexOfMax = max(list)
    indexOfMin = min(list)
    list.remove(indexOfMax)
    list.remove(indexOfMin)
    if(indexOfmax < indexOfMin)
        contine
    else if(indexOfMax == indexOfMin)
        return -1
    else
        SUCCESS
于 2011-02-05T01:23:41.043 回答
0

据我了解（您没有在评论中纠正我），您希望a[i]/a[j]为所有j <= i. 如果这是正确的，那么对于每个i我们只需要知道它之前的最小值。

int current_min = INFINITY;
double max_increase = 0;
for (int i = 0; i < n; ++i) {
    current_min = min(current_min, a[i]);
    max_increase = max(max_increase, a[i] / min);
}
于 2011-02-05T01:23:36.690 回答
0

所以你只想成对比较每个数字，看看哪一对从第二个数字到第一个数字的比率最高？只需迭代两个循环（一个 i=0 到 n，一个内部循环 j=i+1 到 n）就会给你 O(n^2)。我想这实际上是您最初的解决方案，但您错误地说复杂度是 O(n^3)。这是n^2。

不过，您可以达到 O(n log n)。拿你的列表，把它变成一个列表，其中每个元素都是一对（索引，值）。然后按该对的第二个元素对其进行排序。然后有两个指向列表的指针，一个来自左侧（0 到 n-1），另一个来自右侧（n-1 到 0）。找到第一对元素，使得左侧元素的原始索引小于右侧元素的原始索引。完毕。

1 2 3 10 1 20 40 60
becomes
(1,0) (2,1) (3,2) (10,3) (1, 4) (20, 5) (40, 6) (60,7)
becomes
(1,0) (1,4) (2,1) (3,2) (10,3) (20,5) (40,6) (60,7)

所以你的答案是 60/1，从索引 0 到索引 7。

如果这不是您要查找的内容，那么如果您说出示例数字的正确答案会有所帮助。

于 2011-02-06T01:09:29.150 回答
0

如果我正确理解您的问题，您正在寻找数组中的两个索引 (i, j)，其中 i < j 具有最高比率 A[j]/A[i]。如果是这样，那么您可以将其简化为这个相关问题，它要求您找到 i ≤ j 的索引 (i, j)，使得 A[j] - A[i] 尽可能大。这个问题有一个非常快的 O(n) 时间、O(1) 空间算法，也可以适应这个问题。直觉是解决仅由数组的第一个元素组成的数组的问题，然后是前两个元素，然后是前三个元素，等等。一旦你解决了数组的前 n 个元素的问题，你有一个问题的整体解决方案。

让我们想想如何做到这一点。最初，当您仅考虑数组的第一个元素时，通过将元素与其自身进行比较，您可以获得的最佳百分比增加是 0%。现在，假设（归纳地）您已经解决了前 k 个数组元素的问题，并且想看看当您查看下一个数组元素时会发生什么。当这种情况发生时，两个条件之一成立。首先，前 k 个元素的最大百分比增加也可能是前 (k + 1) 个元素的最大百分比增加。例如，如果第 (k+1) 个数组元素是一个非常小的数字，那么您很可能无法从前 k 个元素中的某个值到该值的百分比增加很大。其次，最大百分比增加可能是从前 k 个元素之一到第 (k + 1) 个元素。

结合这两种情况，我们得到前 k + 1 个元素的最佳百分比增加是

  • 前 k 个元素的最高百分比增加，或
  • 从前 k 个元素中的最小元素到第 (k + 1) 个元素的百分比增加。

您可以通过遍历数组元素来实现这一点，跟踪两个值 - 您目前看到的最小值和最大化百分比增加的对。例如，对于您的原始示例数组

1  2  3  10  1  20  40  60

该算法将像这样工作：

       1       2       3       10        1       20       40        60
min        1       1        1       1       1         1        1        1
best     (1,1)   (1, 2)  (1, 3)  (1, 10)  (1, 10)  (1, 20)   (1, 40)  (1, 60)

你会输出 (1, 60) 作为最高百分比的增长。在不同的阵列上，像这样：

3   1   4   2   5

那么算法会这样追踪： 3 1 4 2 5 min 3 1 1 1 1 best (3,3) (3,3) (1,4) (1,4) (1,5)

你会输出 (1, 5)。

整个算法仅使用 O(1) 空间，运行时间为 O(n)，这是一个非常好的解决问题的方法。

或者，您可以考虑通过对数组中的所有值取对数，直接将此问题简化为最大单笔销售利润问题。在这种情况下，如果您找到 log A[j] - log A[i] 最大化的一对值，这等效于（使用对数属性）找到 log (A[j] / A [i]) 被最大化。由于 log 函数是单调递增的，这意味着您已经找到了一对 A[j] / A[i] 达到预期值的值。

于 2011-08-30T20:06:02.340 回答